Infoarena Monthly 2014, Runda 3

[•Teodor94]

Runda 3 va avea loc vineri, 28 Martie la ora 19⁰⁰.
Va uram mult succes!  

[•CosminRusu]

Incepand cu runda aceasta problemele vor fi sortate dupa dificultate?

[•maritim]

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

[•maritim]

Runda s-a incheiat! Clasamentul este public. Felicitari tuturor participantilor! 

[•Mihai22e]

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

[•PlayLikeNeverB4]

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 (stiu, am fost incet)

[•binic]

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 ?

[•Kira96]

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.

[•Cristy94]

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

[•PlayLikeNeverB4]

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

Mie mi-a intrat in 360ms.

[•danalex97]

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

[•Teodor94]

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

[•maritim]

@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

[•florin.elfus]

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

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

E vreun caz particular testu 4?

[•Andrei1998]

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.

[•klamathix]

@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

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

[•narcis_vs]

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

[•binic]

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.

[•Impaler_009]

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   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.

[•geniucos]

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

[•a_h1926]

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.

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

Cod:

10 10 1
1 2 3 4 10 9 8 3 4 5

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 si aici.

[•Impaler_009]

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.

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).

Prea tare argumentul 

[•Cristy94]

@Cristy94 In testul 3 nu trebuia sa inlocuiesti niciun cuvant

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

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

[•binic]

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.

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

Cod:

10 10 1
1 2 3 4 10 9 8 3 4 5

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 si aici.

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

[•Teodor94]

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