infoarena

Runda 3 (http://infoarena.ro/monthly-2014/runda-3) va avea loc vineri, 28 Martie la ora 19⁰⁰.
Va uram mult succes!  :winner1:

Incepand cu runda aceasta problemele vor fi sortate dupa dificultate?

Nu au fost sortate dupa dificultate in cazul acestei runde, dar le postez eu aici in ordinea dificultatii (de la usor la greu) :

• Beep
• Bancomat
• Basequery
• Concert2

Runda s-a incheiat! Clasamentul este public (http://www.infoarena.ro/monthly-2014/runda-3/clasament). Felicitari tuturor participantilor!  :winner1:

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

Felicitari pentru runda :)
Concert2 mi s-a parut mai usoara decat Basequery.
Am retrimis Beep deoarece declarasem sirul rezultat de dimensiune N si trebuia 4N, insa ar fi trecut si fara sa retrimit. Nu exista astfel de test sau coincidenta?
Cam ciudat sa fiu cu 3 probleme pe pagina a 2-a :D (stiu, am fost incet)

Au fost interesante problemele. Din pacate am retrimis bancomat de 2 ori crezand ca 2^31 nu intra in int ](*,). Altfel aveam cam 23 de puncte in plus.
Care era al patrulea test de la concert2 ?

Felicitari pentru runda! Mi-au placut foarte mult problemele, deoarece toate in afara de concert2 mi s-au parut mai mult de idee decat de structuri de date. Mi-a placut mult basequery.Am aflat ca unii au facut-o cu hashuri/mapuri sau doar offline.Eu am facut-o fara hashuri/mapuri si online, sunt curios care e solutia oficiala. =D>

Awe :( http://www.infoarena.ro/job_detail/1157884
Era vreun caz particular pe testul 3?  =D>

Mie mi-a intrat in 360ms.

Frumoasa runda ! Mi-a placut concert2. Felicitari autorilor !  :ok:

Multumim pentru feedback! Felicitari tututor participantilor  :winner1: Pagina cu solutiile va fi publica pana maine, cel tarziu. Va asteptam la runda a 4a!

@Cristy94 In testul 3 nu trebuia sa inlocuiesti niciun cuvant

@Kira96 Solutia oficiala este tot offline. Adauga si solutia ta in articol sa o vedem :)

Mi-a placut runda, in special problema Concert2. In timpul concursului am gasit o solutie in O(N * K1), care aproape merge :roll:

http://www.infoarena.ro/job_detail/1158509

E vreun caz particular testu 4?

Aveti un hint pentru problema cu bazele de numeratie? Multuemsc anticipat. 
Si apropo, m-am prins la problema concert 2 de o solutie O(n*max(k1,k2)*logn) cu normalizare si arbori de intervale, se putea mai smen de atat, nu e nevoie de solutie, hint e suficient.
:thumbup:

Nu e offline solutia oficiala, e doar precalculata. Si Denis precalculeaza, are exact solutia oficiala :)

Pentru testul 4 raspunsul este min(k1,lungimea celui mai lung subsir crescator)

la concert2  eu am gasit o solutie de O(n) dar nu stiu de ce nu mi-a dat pe testul 4. daca vreti va descriu ideea.

Concursul a fost reusit.  Foarte frumoase toate problemele. Am o singura nelamurire: Dupa concursul trecut s-a facut promisiunea ca problemele o sa fie afisate in ordinea dificultatii, insa n-a fost cazul. Tin sa spun ca la un concurs la care esti penalizat pentru timpul pana la submisie si la care problemele variaza foarte mult ca dificultate, insa toate au aceasi valoare ca punctaj, mi se pare foarte important sa le abordezi in ordinea dificultatii. Exista optiunea sa treci prin toate, dar si asta te costa puncte, sau poti sa tii un ochi pe monitorul de evaluare, dar prin asta nu simulezi conditii de concurs. Eu m-am apucat de Bancomat, presupunand ca e cea mai usoara, insa acolo am avut un bug de care mi-a luat mult sa ma prind  :oops: si m-a costat mult timp. Am abordat Beep deabia dupa jumatate de ora si am pierdut astfel puncte gratuite. Poate a fost si o greseala tactica din partea mea (sunt genul care greu lasa o problema dupa ce o citeste) dar ar fi facut o mare diferenta zic eu sa le am in ordinea dificultati. Nu vreau sa o luati ca pe o plangere, doar ca pe o sugestie pentru runda urmatoare.

Cand se pun problemele in arhiva?M-am prins ce am gresit la concert2 si vreau sa vad daca acum merge  :D

Solutia ta este un greedy incorect.

Pentru K1 = N si K2 = 1, problema se reduce la a determina subsirul crescator de lungime maxima si nu poate fi rezolvata intr-o complexitate mai mica de O(N * logN).
Pe testul
raspunsul oferit de solutia ta este 7, iar raspunsul corect este 5.

Edit: problema determinarii subsirului crescator de lungime maxima este celebra in literatura de specialitate si puteti citi mai multe aici (http://en.wikipedia.org/wiki/Longest_increasing_subsequence) si aici (http://www.infoarena.ro/problema/scmax).

Prea tare argumentul  :D

Pai vad ca mie imi da bine cand nu trebuie sa inlocuiesc nimic :( Poti sa imi trimiti testul prin PM, chiar sunt curios de ce nu merge :D

LE: Cred ca am gasit greseala, aveam un < in loc de <=  :banana:

Multumesc pentru ca m-ai lamurit. Astept solutiile oficiale. Nu m-am gandit la acest caz.

Am adaugat solutiile oficiale pe pagina solutiilor. Daca aveti si alte solutii, va incurajam sa le postati!

Ai folosit arbori indexati binar sau arbori de intervale?

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.

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.

Eu am facut cu cautare binara.

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

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

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.

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.

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

Ce tare. Se pare ca e corect.

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  :-k, 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.  :thumbup:

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