013 Progr2

[•Teodor94]

Aici puteţi discuta despre problema Progr2.

[•PlayLikeNeverB4]

Trebuia mai bine decat O(T*N^2)? Cum?

[•Teodor94]

Solutia oficiala este O( T * N ^ 2 ) cu hashuri.

[•PlayLikeNeverB4]

Ciudat. Exact asa am facut. Sursa aceasta ia TLE. Trebuia hash de mana?

[•darren]

Numerele lui Georgică sunt distincte.

Am testat si nu cred ca este respectata aceasta conditie pe toate testele.

[•PlayLikeNeverB4]

  Ai dreptate!

[•mugurelionut]

Mie mi-a intrat in timp O(N^2 * log(N)) per test - si asta folosind map-uri din STL, care sunt destul de lente (comparativ cu a cauta elemente intr-un vector sortat folosind cautare binara). Ce-i drept, am avut probabil noroc, caci timpul de rulare a fost foarte la limita: 1.484 sec din 1.5 sec.

[•Teodor94]

Asa este. Imi cer scuze pentru greseala. Am sa modific testele si sa reevaluez sursele din arhiva cat mai curand.

LE: Testele au fost modificate. Restrictia lui Georgica este respectata acum. Imi cer scuze inca odata pentru greseala.

[•PlayLikeNeverB4]

Ma ajuta cineva sa inteleg de ce iau TLE? Am postat sursa mai sus.

[•mugurelionut]

Ma ajuta cineva sa inteleg de ce iau TLE? Am postat sursa mai sus.

Eu nu pot sa iti vad sursa. Nu cred ca sursele trimise la problema asta sunt publice.

[•PlayLikeNeverB4]

Ca sa o poti vedea cred ca trebuie sa trimiti sursa de 100 si in Arhiva ACM

[•mugurelionut]

Ca sa o poti vedea cred ca trebuie sa trimiti sursa de 100 si in Arhiva ACM

OK. Done. Asa am putut sa-ti vad sursa si sa o fac sa ia 100.
Se pare ca partea time-consuming este introducerea in map. Ca sa intre in timp trebuie sa introduci toate elementele in map la inceput. Apoi, cand calculezi pos in for-ul interior, mai adaugi conditia ca pos>j.

[•PlayLikeNeverB4]

Multumesc mult!