880 Unique

[•DITzoneC]

Aici puteţi discuta despre problema Unique.

[•wefgef]

Am schimbat limita de timp si am reevaluat.

[•bogdan2412]

Cu limita de timp 0.7 sursele cu complexitate O(N * log N) nu luau decat 40 de puncte, la fel cat un brut. Am modificat limita de timp la 1.2 secunde si acum se poate lua 70 de puncte cu complexitate N * log N si totusi se face departajare clara intre bruturi optimizate, O(N * log N) si O(N * log* N). Am reevaluat si nu s-a schimbat niciun punctaj cu exceptia a doua surse care aveau complexitate N * log N ale lui mihai_florea, care obtineau 40 de puncte si acum obtin 70. Mi se pare mai bine asa.

[•wefgef]

Tu ai aint acolo... daca faci cu aib sigur nu intra in timp?

[•bogdan2412]

Cum faci cu aib? In solutia mea, imi tb un minim pe intervalul (1, i) dar valorile cresc pe masura ce cresc i-ul, deci nu merge aib.

[Later edit] Am trimis sursele lui gcosmin si devilkind din concurs care sunt cu aib-uri si iau 70 de puncte. Merg in 1.4 secunde, respectiv 1.3 secunde. Se poate scadea limita de timp la 1.1 sau 1 secunda si solutiile N log N sa obtina 70 de puncte la limita. Ti se pare ok asa?

[•wefgef]

Pare bine cu limita de 1.1

[•Mishu91]

Poate povesti cineva despre soluția in N*(log*N), pentru că nu prea văd cum aș putea să țin mulțimile disjuncte astfel încât să aflu dacă într-un interval apar toate numerele de la 1 la valoarea maximă.

[•katakuna]

Unde pot gasii solutiile problemelor de la baraj din ziua a 2-a ? 

[•dornescuvlad]

Unde pot gasii solutiile problemelor de la baraj din ziua a 2-a ? 

Le-am gasit pe pagina CNLR Bistrita.
Link: http://www.cnlr.ro/?pagina=358

[•scipianus]

Imi poate da cineva vreun indiciu despre cum s-ar folosi AIB/AInt pentru a afla cate elemente distincte se afla intr-un interval (asa cum se precizeaza in solutia oficiala)?

[•S7012MY]

http://infoarena.ro/problema/distincte
http://www.spoj.pl/problems/DQUERY/

[•scipianus]

http://infoarena.ro/problema/distincte
http://www.spoj.pl/problems/DQUERY/

Gata,am priceput Culmea e ca facusem problema Distincte,dar nu ma gandisem si pentru problema Unique la partea aia sa sortez intervalele de query Mersi

Poate sa se uite cineva pe sursa mea sa-mi zica ce as putea optimiza?  http://infoarena.ro/job_detail/754358?action=view-source Ia 40 (de fapt 60,dar testele sunt grupate) cu TLE,desi fac AIB

[•a_h1926]

Eu am luat 100 folosind o solutie cu complexitate liniara (am folosit paduri de multimi disjuncte), dar imi intra in 0.25 secunde, si e posibil ca o solutie NlogN sa nu mai intre in timp. Cata vreme nu iei WA-uri, inseamna ca solutia ta cu AIB-uri e corecta (chiar daca nu intra in timp), si poti sa incerci si solutia cu paduri de multimi disjuncte. Daca nu iti iese, trimite-mi un mesaj si iti explic mai detaliat cum am facut eu.

[•wefgef]

Poate sa se uite cineva pe sursa mea sa-mi zica ce as putea optimiza?  http://infoarena.ro/job_detail/754358?action=view-source Ia 40 (de fapt 60,dar testele sunt grupate) cu TLE,desi fac AIB

Solutia cu AIB nu ar trebui sa ia 100 de puncte.

[•Florian]

Solutia cu AIB nu ar trebui sa ia 100 de puncte.

Eu am 100 cu AIB.

LE: Acum am vazut, ca de fapt am citirea parsata  Scuze.

[•vendetta]

Salut! Am complexitatea O(T * N * log N) si iau 30 de pct cu TLE pe restul. Probabil 100 nu ia solutia asta dar n-ar trebui sa ia mai mult de 30 ?

[•pauldb]

Conteaza si cum ai implementat. Solutia de 100 de puncte e super misto, merita departajarea mai dura.

[•vendetta]

Chiar asa de dura incat solutia mea sa ia acelasi punctaj ca un brut?! Cred ca trebuie marita limita pentru ca am vazut din mesajele postate anterior ca se lua 70.

[•SebiSebi]

Poate detalia cineva solutia cu paduri de multimi disjuncte? Am vazut ca in solutia oficiala nu este descrisa ci doar precizata. Multumesc!

[•dariusdarius]

As dori sa precizez ca am implementat o solutie in O(N * logN), cu AIB-uri si sort-ul din STL care obtine 100 de puncte cu citirea parsata. As putea propune schimbarea testelor din format clasic intr-unul in care se dau primele cateva numere si restul se genereaza din ele, pentru a preveni astfel de "bulaneli" pe viitor 

[•klamathix]

Chestia e că în momentul în care dai inputul printr-un generator, pierzi control asupra structurii testului. Dacă vrei să numeri inversiuni, spre exemplu, n-ar fi nicio problemă să dai permutarea random, fiindcă nu te interesează cum arată. Nu prea se pot bulăni inversiunile. Dar la problema asta se poate bulăni, deci ar fi cam nasol să lași testele la voia generatorului .

[•oldatlantian]

Un mic hint pentru cei ce vor sa bage problema in O(N log N): bucket sort is your friend.