Infoarena Monthly 2014, Runda 3

[•Mihai22e]

O limita un pic mai mare la concert2.. totusi, http://www.infoarena.ro/job_detail/1158352 e trist

Mie mi-a intrat in 360ms.

Ai folosit arbori indexati binar sau arbori de intervale?

[•geniucos]

Eu am facut cu AIB si mi-a intrat in 88 ms.Cu arbori de intervale probabil ca e mai incet dar nu cred ca e asa mare diferenta.Uita-te sa nu apelezi vre-un query pe intervalul 1,0 sau 0,0 sau asa ceva.

[•binic]

Dupa mine concert2 avea complexitate maxima de O(N*logN). Daca k1>1 si k2>1 atunci chiar intra in O(N), iar daca unul dintre ele era 1 atunci era cel mai lung subsir crescator. Multumesc lui Andrei Heidelbacher pentru observatia de mai sus, acel greedy nu e corect daca k1=1 sau k2=1.

[•PlayLikeNeverB4]

Eu am facut cu cautare binara.

[•Bogdanisar]

http://www.infoarena.ro/job_detail/1158354
Era vreun caz particular la testul 1 ?

[•Cristy94]

Dupa mine concert2 avea complexitate maxima de O(N*logN). Daca k1>1 si k2>1 atunci chiar intra in O(N), iar daca unul dintre ele era 1 atunci era cel mai lung subsir crescator. Multumesc lui Andrei Heidelbacher pentru observatia de mai sus, acel greedy nu e corect daca k1=1 sau k2=1.

Poti sa explici ideea ta de solutie in O(N)?...

[•binic]

Daca aveam k1>1 si k2>1 atunci o secventa descrescatoare/crescatoare poate sa fie reprezentata de primul si ultimul element si alte elemente din mijlocul secventei. Atunci parcurgem sirul si pur si simplu, verificam fiecare secventa crescatoare si adunam min(k1,lungimea_secventei_crescatoare), la fel si la secventele descrescatoare. Evident trebuie sa avem grija sa nu adunam un element de 2 ori. Cum am zis mai sus, daca k1=1 sau k2=1 trebuie sa calculam cel mai lung subsir crescator/descrescator. Daca nu intelegi mai explic.

[•PlayLikeNeverB4]

Eu nu cred ca are cum sa fie corect un greedy. Poti sa incerci sa implementezi ideea ta pe cazul k1>1 si k2>1 si pentru celelalte cazuri cel mai lung subsir crescator/descrescator.

[•binic]

Am implementat-o si am luat 100, dar in timpul concursului nu am luat cazul cu cel mai lung subsir crescator .

[•PlayLikeNeverB4]

Ce tare. Se pare ca e corect.

[•Andrei1998]

Update-ul de rating nu a intaziat, insa, din pacate, nu a fost facut corespunzator. Dupa runda a doua a concursului de fata, a avut loc ONIS Runda 3 (care, corectati-ma daca gresesc  , este concurs cu rating). Rog sa se anuleze ultimul update de rating, sa se face update-ul pentru ONIS Runda 3 si apoi, in incheiere sa se face update-ul pentru runda 3 Monthly. Scriu acest mesaj pentru ca dupa aia mai are loc inca un concurs, doua si chiar devine foarte greu de reparat aceasta mica greseala. 

[•Mihai22e]

Update-ul de rating nu a intaziat, insa, din pacate, nu a fost facut corespunzator. Dupa runda a doua a concursului de fata, a avut loc ONIS Runda 3 (care, corectati-ma daca gresesc  , este concurs cu rating). Rog sa se anuleze ultimul update de rating, sa se face update-ul pentru ONIS Runda 3 si apoi, in incheiere sa se face update-ul pentru runda 3 Monthly. Scriu acest mesaj pentru ca dupa aia mai are loc inca un concurs, doua si chiar devine foarte greu de reparat aceasta mica greseala. 

Din ce am inteles eu, s-a decis ca ONIS Runda 3 sa ramana unrated.