005 Permutari

[•fluffy]

Aici puteţi discuta despre problema Permutari.

[•stifmeister]

Am demonstrat ca rezultatul este de fapt numarul lui Stirling

de speta intai |s(N,K)|, unde N si K sunt numerele din problema.

Am determinat s(N,K) cu formula de recurenta:
s(N,K) = (N-1)s(N-1,K) + s(N-1, K-1).
   Desi atat formula cat si calcularea ei recursiva mi se par

corecte ( sunt demonstrate in "Probleme de combinatorica si teoria

grafurilor" de Ioan Tomescu, Editura Didactica si Pedagogica,

1981, pag. 51) sursa mea este evaluata la 10 puncte.
  De ce?

[•gogu]

tu ai bagat operatii pe numere mari?

[VladS]

Ce primesti Wrong Answer sau Time limit exceeded?

Ce numar stirling ai folosit? Primul sau al doilea?
Poate exista o formula nerecurenta, ca la combinari, care se poate calcula mai usor.

[VladS]

Apropo, stie cineva de unde imi pot cumpara I. Tomescu "Probleme de combinatorica si teoria grafurilor?". Exista vreo editie mai noua? Din cate stiu eu cartea e antica.

[•bogdan2412]

Tu esti sigur ca ai dem bine? Din cate am facut eu pe foaie nu e bine. M-am uitat pe http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html sa vad exact ce sunt numerele lui Sterling.
De ex pt 3 rezultatele ar fi 2, 3 si 1 (nu 1,3 si 1), iar pt 4 sunt 6,11,6 si 1, nu(1,7,6,1). Asta dc am inteles bine problema.

[•stifmeister]

Am sa raspund la toate mesajele:
1. am implementat operatii pe numere mari de pana la 500 de cifre

(iar din calculele mele cel mai mare numar se obtine pentru 200 si 2 sau 200 si 3 si nu are decat 370 si ceva de cifre, un pic mai mult decat 200!).
2. folosesc primul numar al lui stirling, primesc "Wrong answer"

iar tmpul de executie este sub 0.05 sec (pt N=200).
3. pt Bogdan2412: ce ai gasit tu este nr lui Stirling de speta a

doua, care este cu totul altceva. Si am inteles bine problema. Pt n = 5, obtin 24, 50, 35 (ca in exemplul din problema), 10 si 1. Nu-i asa?

Acesta e textul problemei din "Probleme de combinatorica si teoria
grafurilor":
12.15 Demonstrati ca numarul permutarilor p ale multimii {1,2,...,n} care au proprietatea ca exista exact k elemente j pentru care p(j)>p(i) pentru orice i<j este egal cu |s(n,k)|.


|s(n,k)| numarul lui Stirling de speta intai si este egal cu coeficientul lui x^k din dezvoltarea: x(x+1)(x+2)...(x+n-1).


Daca doreste cineva am sa pun pe forum si demonstratia lui Ioan Tomescu.

[•stifmeister]

Poate ma ajuta cineva care a luat maxim la problema asta.

Am rulat cateva teste:
1. N=13; K=8; Am obtinut sol = 1095154;
2. N=17; K=4; Am obtinut sol = 87077748875904;
2. N=70; K=45; Am obtinut
 sol = 26269688897329413126924403900781315211553781164470;

Va da si voua la fel?

[•domino]

Poate ma ajuta cineva care a luat maxim la problema asta.

Am rulat cateva teste:
1. N=13; K=8; Am obtinut sol = 1095154;
2. N=17; K=4; Am obtinut sol = 87077748875904;
2. N=70; K=45; Am obtinut
 sol = 26269688897329413126924403900781315211553781164470;

Va da si voua la fel?

Pentru primul raspunsul este 6926634
Pentru al doilea este 87077748875904 (aici iti da bine)
Iar pentru al treilea imi da 328693139125599643512870879273574455866682562802025734100

[•ManolacheAdrian]

Cel mai probabil ai gresit la implementarea operatiilor cu numere mari,
Daca foloseai int64 obtineai 40p.
Rezultatul pentru n=13 si k=8 este 6926634.

[•bogdan2412]

@stifmeister: scuze... oricum, probabil ai gresit ceva la calcularea numerelor mari.

Eu am facut problema, dar la 9/10 teste am primit "RUN ERROR - Invalid memory reference". Am facut o clasa cu numere mari, reprezentarea unui numar mare am facut-o pe un vector int de 1001. Am folosit doi vectori de tip numar mare de dim 201 pt calcularea solutiei. Am verificat problema acasa pe 200 2 si 200 100 si 200 199 si nu am primit nici un mesaj Segmentation Fault... Ma poate ajuta cineva?

[•stifmeister]

Va multumesc, am rezolvat problema si am luat 100p. Formula era buna dar am gresit la

implementarea adunarii numerelor. Era un caz particular si de-aia nu m-am prins repede unde

am gresit.

[•LucAnd]

am facut si eu problema bazat pe aceeasi formula de recurenta , am facut si pe numere mari si pe mici , si tot iau 40 puncte , tot imi iese din timp , cand intra in recurenta cu k mare trebuie sa astept mult
Voi ce conditii de iesire aiti folosit??
eu pt n=k am gasit sa stir=1 si pt k=1 am gasit k=1 stir=(n-1)!
da in ritmu asta progrmu mere greu poate am ratat eu o chesti asa ca pls help

nu mai conteaza am gasit solutia , eu am facut o implementare simpla si directa si aceeasi valoare era calculata de f multe ori , am modificat algoritmul astfel incat sa se retina valorile obtinute si sa se refeoloseasca cand e nevoie am luat 100 p

[edited by svalentin] posts merged; nu mai postati dublu! daca aveti ceva de adaugat folositi "edit"!!

[•peanutz]

Folosesc numere mari, dar iau 60, pe 4 teste iau tle.. Am optimizat cat am putut, dar nu-mi dau seama ce s-ar mai putea face.. Aceasta este implementarea pe numere mari....

Cod:

void aduna(int j, int b)
{
int i, t;

for(i = 1, t = 0; i <= old[j-1][0]  || i <= old[j][0]  ||  t  ||  i <= curent[j][0]; ++i, t /= 10)
	curent[j][i] = (t += old[j][i]*b + curent[j][i] + old[j-1][i]) % 10;

curent[j][0] = i-1;
}

old e linia anterioara, curent e linia curenta...

Sugestii?

[•bogdan2412]

Poti incerca sa folosesti baza 10000 sau 10^6 pentru numere.

[•peanutz]

ok, am sa incerc, multumesc!


Later edit:
Ok, am gasit ce nu faceam bine... eu la fiecare pas puneam 'curent' pe 0... ceea ce era.... oricum, am sa incerc si varianta cu baza, pare interesant...

[•C_Ovidiu]

 Nu stiu daca am inteles prea bine problema .  Nu  posteaza cineva sirurile de lungime 3 cu 2 maxime ?

[•devilkind]

231
132
213

[•Qbyx]

Poate sa-mi scrie cineva daca a facut 100 ... cat e timpul la testul 5 si 8?
Eu la testul 5 totdeauna am TLE  ... si la testul 8 da 300 ms hlp pls (sry bad roman)

[•pauldb]

Limita de timp pe toate testele este de 0.3 s [sau 300 ms]. Testele nu sunt neaparat ordonate in ordinea dificultatii. Oricum, mai optimizeaza.

[•Qbyx]

Stiu ca limita de timp e 0.3 ms dar vreau sa stiu timpul la testul 5 cine a facut 100, pentur ca daca e foarte mica (20-80 ms) atuci nu n sau k e mare ci am o problema in program cu numerele mici. ..la testul 8 am primit eu 300 ms exact cat trebuie de aceea am 90 puncte...Si poti sa-mi dai niste idee de optimizare?

[•pauldb]

Ti-as zice ce timpi am pe testul respectiv, dar sursa am trimis-o pe infoarena 1. Ca optimizari ai putea sa calculezi numerele mari intr-o baza mai mare (gen 10000) si sa nu calculezi toate starile din dinamica, ci doar alea de care ai nevoie pentru a obtine rezultatul.

[•stef2n]

Pe testul 5 sursa mea ruleaza in 288ms, iar pe testul 8 ruleaza in 252ms

[•devilkind]

si mie mi-a intrat cam cu aceeasi timpi aproximativ folosind baza 10.

[•Qbyx]

Da nu calculez nici unu in plus (asa a fost) dar am incercat baza 10^4 si am resuit!!!
Acum timpul la testul 5 e 72 ms  ... Thx