|
Titlul: 013 Progr2 Scris de: Teodor Plop din Ianuarie 12, 2014, 15:09:56 Aici puteţi discuta despre problema Progr2 (http://infoarena.ro/problema/progr2).
Titlul: Răspuns: 013 Progr2 Scris de: George Marcus din Ianuarie 12, 2014, 17:32:45 Trebuia mai bine decat O(T*N^2)? Cum?
Titlul: Răspuns: 013 Progr2 Scris de: Teodor Plop din Ianuarie 12, 2014, 22:03:28 Solutia oficiala este O( T * N ^ 2 ) cu hashuri.
Titlul: Răspuns: 013 Progr2 Scris de: George Marcus din Ianuarie 12, 2014, 22:43:22 Ciudat. Exact asa am facut. Sursa aceasta (http://www.infoarena.ro/job_detail/1080857?action=view-source) ia TLE. Trebuia hash de mana?
Titlul: Răspuns: 013 Progr2 Scris de: Rares Buhai din Ianuarie 13, 2014, 09:24:28 Citat Numerele lui Georgică sunt distincte. Am testat si nu cred ca este respectata aceasta conditie pe toate testele.Titlul: Răspuns: 013 Progr2 Scris de: George Marcus din Ianuarie 13, 2014, 11:43:04 :shock: Ai dreptate!
Titlul: Răspuns: 013 Progr2 Scris de: Mugurel-Ionut Andreica din Ianuarie 14, 2014, 01:40:21 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.
Titlul: Răspuns: 013 Progr2 Scris de: Teodor Plop din Ianuarie 14, 2014, 22:38:34 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. :sad: Titlul: Răspuns: 013 Progr2 Scris de: George Marcus din Ianuarie 15, 2014, 21:03:51 Ma ajuta cineva sa inteleg de ce iau TLE? Am postat sursa mai sus.
Titlul: Răspuns: 013 Progr2 Scris de: Mugurel-Ionut Andreica din Ianuarie 16, 2014, 02:38:52 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.Titlul: Răspuns: 013 Progr2 Scris de: George Marcus din Ianuarie 16, 2014, 07:37:21 Ca sa o poti vedea cred ca trebuie sa trimiti sursa de 100 si in Arhiva ACM :D
Titlul: Răspuns: 013 Progr2 Scris de: Mugurel-Ionut Andreica din Ianuarie 17, 2014, 01:22:55 Ca sa o poti vedea cred ca trebuie sa trimiti sursa de 100 si in Arhiva ACM :D 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. Titlul: Răspuns: 013 Progr2 Scris de: George Marcus din Ianuarie 17, 2014, 09:49:31 Multumesc mult! [-o<
|