005 Permutari

[•Bluedrop_demon]

Nu pricep. Aplic formula, calculez recursiv si folosesc int64. Normal daca da pe afara cred ar trebui sa dea un fel de eroare sau sa devina valorile negative dar imi da TLE. Folosind operatii pe numere mari nu ar dura si mai mult ?

[•astronomy]

Recursivitatea e mai inceata.

[•Bluedrop_demon]

Am facut in baza 10^4 si am luat 100p.  Super problema, chiar am avut de invatat niste cazuri particulare in la operatiile cu numere mari. Eu programator inrait pe borland a trebuit sa fac multe schimbari pe agoritm sa functioneze de 100 in fpc. Oricum, multumesc mult pentru sfaturi!

[•nash]

 ok .. ceva nu imi iese mie .. bine si nu vad unde gresesc ...
     Eu gandesc in felul urmator  :
       folosesc o matrice sol[ i ][ j ] care reprezinta numarul de permutari cu "i" elemente care au "j" maxime . O permutare cu "n" elemente si "k" maxime se poate forma din :
                    - o permutare cu "n-1" elemente si "k-1" maxime prin adaugarea elementului "n" la sfarsitul permutarii .
                    - o permutare cu "n-1" elemente cu "k" maxime prin adaugarea elementului "n" inaintea ultimului maxim.
                    - o permutare cu "n-1" elemente cu "k+1" maxime prin adaugarea elementului "n" inaintea ultimelor doua maxime .
             ....................................
             ....................................
                   - o permutare cu "n-1" elemente cu "n-1" maxime prin adaugarea elementului "n" dupa primele "k" elemente din permutare .

       De aici rezulta ca numarul de permutari cu N elemente si K maxime se calculeaza in felul urmator :

sol[ n ][ k ] = sol[ n-1 ][ k-1 ] + sol[ n-1 ][ k ] + sol[ n-1 ][ k+1 ] + ... +sol[ n-1 ][ n-1] 
initial sol[ 1 ][ 1 ] = 1

Calculand in felul acesta nu se ajunge la rezultatul corect .

1
1 1
2 2 1
......
in loc de al doilea 2 corect era "3" .. ( se poate vedea ca e si exemplu dat ...) nu vad unde gresesc .. evident .. nu va merge pentru teste mari .. insa .. nu vad unde gresesc .. ( ma refer la ideea de rezolvare )

   Nu poate nimeni sa imi dea nici un sfat .. sau toti cei care pot sunt la baraj pentru lot ??    
 
 

[•cos_min]

Ai gresit recurenta.
Defapt problema cere sa determini numarul lui Stirling de speta intai.
s(N,K) = (N-1)s(N-1,K) + s(N-1, K-1).

[•nash]

 Am vazut ca au afisat cineva la inceputul topicului striling de speta 1 ... insa .. eu vream sa stiu ce e gresit in gandirea mea ....

[•pauldb]

Tu pentru k+p maxime te gandesti ca poti introduce elementul N inainte de ultimele p-1 maxime. Problema este ca s-ar putea sa ai mai multe locuri in care sa-l poti introduce.

Uite un exemplu:

3 2 1 4 5

Vrei sa obtii doua maxime cand bagi pe 6 si poti obtine:

3 6 2 1 4 5
3 2 6 1 4 5
3 2 1 6 4 5

In recurenta ta, aduni o singura data.

[•nash]

  Ah da .. corect .. nu m-am gandit la asta merci ..

[•vicenzo_cnu]

Am si eu o problema ... fac problema prin numerele lui stirling, afisez cu numere marisi totusi imi da WA la 4 teste, am incercat cu 10^4 afisarea pana la 10^9... tot 4 teste gresite imi da, dar culmea culmilor este k testele gresite nu coincid knd schimb baza de afisare  ... poate cineva sa-mi spuna care-i faza 

[•stef2n]

Ai grija cand folosesti o baza mai mare ca 10 sa afisezi si zerourile. De exemplu, daca folosesti baza 10^4, numarul 73 trebuie afisat ca 0073.

[•vicenzo_cnu]

Ms mult pentru observatie... am luat si eu suta 

[•cos_min]

Cat va da pentru :

Cod:

200 2

Cred ca asta ii cel mai mare rezultat care se poate obtine.

[•stef2n]

Cod:

23159060312564359871950929055455674021435236167923959343115750040823047581979908380727537796461185778013737134426559431288744237478343902437539133012028435084567718670531340662889488184573823549876303454548719715122034588710323516710029845203752585692844797698070034630498657231556170312181971812010087147350420585907013230054604800000000000000000000000000000000000000000000

[•xtreme]

Cum as mai putea sa-mi optimizez solutia ca sa iasa in timp?
http://infoarena.ro/job_detail/164223

[•fireatmyself]

foloseste baza 10000 pentru numerele mari. ai grija la afisare.

[•devilkind]

el ia 9 tleuri deci probabil ca face back. Nu cred ca il ajuta sa mareasca baza la numere. Incearca sa te gandesti la alta abordare.

[•gabitzish1]

E greu sa dai indicatii daca nu stii ce e in sursa aia... Alex, descrie putin ce faci acolo.
Dupa numarul de teste care depasesc timpul, probabil Devilkind are dreptate : incearca altceva.

[•xtreme]

E greu sa dai indicatii daca nu stii ce e in sursa aia... Alex, descrie putin ce faci acolo.
Dupa numarul de teste care depasesc timpul, probabil Devilkind are dreptate : incearca altceva.

Generez toate permutarile si dupa aceea verific cate maxime are....daka are k maxime afisez solutia...

[•stef2n]

Cauta o solutie mai eficienta. Iar daca nu te prinzi, citeste cu atentie posturile anterioare din topicul asta.

[•theratman]

am si eu o problema
am facut functia de stirling pe nr mici
folosind formula
s(n,k)=(n-1)*s(n-1,k)+s(n-1,k-1)
si la testul n=5 si k=3 imi da 34 si nu 35
ma poate ajuta cineva va rog

[•k_ounu_eddy]

Va rog scrieti demonstratia,ca eu nu am inteles de ce solutia acestei probleme e formula asta:s(N,K) = (N-1)s(N-1,K) + s(N-1, K-1).

[•ghitza_2000]

vreau si eu sa va intreb ceva... am facut sirul stirling... dar din pacate iau decat un test din toate... testul 6 mai precis.... puteti sa imi dati testul 1 sau 2 sa vad care e problema?

Cod:

s[1,1]:=1;  s[2,1]:=1; s[2,2]:=1;
for i:=3 to n do
begin
s[i,1]:=1;
for j:=2 to i-1 do
s[i,j]:=j*s[i-1,j]+s[i-1,j-1];
s[i,i]:=1;
end;

Editat de moderator: Foloseste tag-ul code cand postezi cod!

sigur sunt testele bune? sirul stirling arata pentru 5 3 varianta 25...

Editat de moderator: Nu posta in continuu, ci editeaza mesajele precedente daca sunt pe aceeasi tema.

[•pauldb]

Testele sunt bune. Nu ti se pare ciudat ca au luat si altii 100, daca testele sunt gresite?

Mai sunt pe acest topic cateva teste, le-ai incercat?

[•wefgef]

Ghitza, tu ai inteles problema... sau ai citit pe forum ca se face cu Stirling si ai cautat pe google relatia de recurenta?

[•ghitza_2000]

am citit pe forum;)) si nu imi da ceva bine... dar nu inteleg, cum s-ar putea face?