162 12-Perm

[ditzone]

Aici puteţi discuta despre problema 12-Perm.

[•cristy]

hmm...trebuie sa scot formula pentru sol[n], pentru ca nu prea imi iese...iau 60 de pct, TLE pe restu, si am facut cea mai simpla kestie, un soi de fibonacci, m-am inspirat din solutia oficiala...fara vector, doar cu 3 variabile...

[•filipb]

Ce formula? Cu un for ar trebui sa iasa... E o recurenta liniara acolo de pas 2, care se poate rezolva ( pui ecuatia caracteristica, etc ). Daca vrei te poti uita in Tomescu arata acolo mai clar decat pot eu explica cum se face. Desi sa stii k o sa iti iasa suma de doua numere reale ridicate la o putere naturala, deci nu prea ai cum sa calculezi mai repede ( informatic vorbind )...

[•cristy]

am citit solutia, am un for in care fac un calcul, si 3 atribuiri, si imi iese din timp...

[•wefgef]

cum faci operatia mod?

vezi ca iti zice acolo ca tre sa afiesezi modulo 2^20 (si nu un numar oarecare).

[•fireatmyself]

a mod 2^k <-> a & ((2^k)-1), echivalenta care se demonstreaza banal  

[•cristy]

tot nu merge...o fi din cauza pascalului?

[•wefgef]

eu tot in pascal am facut si mi-a mers.

[•pauldb]

Nici mie nu mi-a intrat in timp (si eu lucrez tot in Pascal), dar am facut urmatorul smen: am declarat un array de constante care retinea cele trei numere necesare din 100000 in 100000. Folosindu-te de aceste constante iti va intra programul in timp si ai si memorie destula. Bafta!

[•filipb]

tot nu merge...o fi din cauza pascalului?

Merge si fara smenuri, da' ai grija sa retii doar ultimele 4 elemente. Si pentru asta ai o coada circulara de dimensiune 4... Trebuie sa mearga!

[•cos_min]

interesant ... iau 60 de pcte cu o sursa : memorie , in loc de sir folosesc 3 variabile si k si complexitate O(n) ... dc?

[•cos_min]

iei dupa ceva timp, am reusit sa rezolv de 100

[•Darth_Niculus]

 Pana la urma s-a aflat dc nu mergea 100 pct cu O(N)? Adica eu am ceva de genu....
   

Cod:

    intializez pe R2,R3,R4
    pentru 5 catre N
             {
              aux=R4;  
              R4 = formula  %  constanta aia
              R2 = R3; R3=aux;
             } 
    

    Si iau 80 pct cu TLE pe ultimele cateva teste....  in ciuda faptului ca "virgula" complexitatea e O(N) si nu cred ca se poate mai bine de atat.

[•cos_min]

Probabil de aici ai TLE : numerele intra in int 

Tipul long long este mai lent cu mult decat tipul int.

[•astronomy]

Merge de 100 in O(N) atat ca trebuie sa tii cont de faptul ca operatia % este mare consumatoare de timp, cum scrie si mai sus in loc de % poti folosi faptul ca numarul acela este 2^20. Nu mai folosi % decat atunci cand nu ai ce face.

[•Darth_Niculus]

 Tnx, am invatat ceva nou azi

[•Bogdan_tmm]

e chiar asa mare diferenta intre

Cod:

           x[0]=x[4]+x[2]+2*(i-2);  
            x[2]=x[3];x[3]=x[4];  
            x[4]=(x[0])&((c)-1); 

si

Cod:

			aux=x[4];
			x[4]=(x[4]+x[2]+2*(i-2))&(c-1);
			x[2]=x[3];x[3]=aux;

.Eu as zice ca primul e mai rapid insa ma insel. imi explica si mie cineva dc?

[•SpiderMan]

Vedeti ca nr. la care trebuie facut restul este o putere a lui 2. Asadar, x % MOD = x & ( MOD - 1); Eu asa am luat de la 65 la 100.

[•andreiulian]

Eu nu inteleg cum se ajunge la relatia de recurenta. Ma poate ajuta cineva?