ONIS 2014 Feedback

[•Kira96]

Cand o sa fie runda 3?

[•Teodor94]

O sa fie anuntata in curand pe pagina principala.

[•comisia]

Nu mai tin minte cum e la acm dar ar fi misto sa nu se ia in calcul erorile de compilare pentru ca acasa avem versiuni diferite de compilatoare fata de cele de pe infoarena

[•mugurelionut]

Are cineva niste teste mai "interesante" la problema Talent? Jumatate din timpul de concurs l-am pierdut incercand sa gasesc teste pe care solutia mea nu este corecta, insa nu am reusit. Am scris si un brute sa verific teste generate de mine cu N pana in jur de 20. In clasament vad ca sunt concurenti care au luat AC dupa mai multe incercari, asa ca daca puteti share-ui din testele cu care v-ati debug-at sursa, ar fi super.

[•Andrei1998]

Frumoasa runda, setul de probleme a fost ales astfel incat sa trebuiasca sa "sti din toate" ca sa ocupi un loc fruntas. Mare pacat pentru acea neclaritate (mai bine spus greseala) din enuntul de la problema puncte3. In rest nu prea am ce comenta pe latura organizatorica a concursului.

[•overflow]

Felicitari pentru probleme si organizare, a fost o runda reusita. Gg easy

[•DraStiK]

Are cineva niste teste mai "interesante" la problema Talent? Jumatate din timpul de concurs l-am pierdut incercand sa gasesc teste pe care solutia mea nu este corecta, insa nu am reusit. Am scris si un brute sa verific teste generate de mine cu N pana in jur de 20. In clasament vad ca sunt concurenti care au luat AC dupa mai multe incercari, asa ca daca puteti share-ui din testele cu care v-ati debug-at sursa, ar fi super.

Cod:

10
01:21 02:22
00:53 02:03
04:53 05:03
20:17 20:54
20:45 22:11
20:30 21:46
03:11 04:44
01:44 02:06
09:37 10:16
23:46 01:17

Cod:

389

[•UVS_Elfus_Deneo_Kira]

Mda, foarte inspirat sa se observe o greseala fatala dupa 4 ore de concurs.  #mlc

[•Robert29]

ce gresala denis?

[•Vman]

Mda, foarte inspirat sa se observe o greseala fatala dupa 4 ore de concurs.  #mlc

Sunt destul de sigur ca problema se putea rezolva si cu limitele initiale 

[•UPB_MIREA_AVRAM_BOACA]

La problema alegeri am incercat urmatoarea idee . Luam muchiile din graful initial,  pe muchiile bune puneam cost 0 iar pe cele stricate puneam costul pe care il citeam . Apoi construiam APM-ul pentru graful acesta si afisam valoarea. In cazul in care nu puteam construi APM-u , (graful nu era conex) afisam -1. Ce e gresit la abordarea asta ?

[•CosminRusu]

La problema alegeri am incercat urmatoarea idee . Luam muchiile din graful initial,  pe muchiile bune puneam cost 0 iar pe cele stricate puneam costul pe care il citeam . Apoi construiam APM-ul pentru graful acesta si afisam valoarea. In cazul in care nu puteam construi APM-u , (graful nu era conex) afisam -1. Ce e gresit la abordarea asta ?

Pe aceeasi idee am luat 100, probabil e de la implementare. Ai grija sa resetezi vectorii si multimile disjuncte (daca faci Kruskal).

[•mugurelionut]

Are cineva niste teste mai "interesante" la problema Talent? Jumatate din timpul de concurs l-am pierdut incercand sa gasesc teste pe care solutia mea nu este corecta, insa nu am reusit. Am scris si un brute sa verific teste generate de mine cu N pana in jur de 20. In clasament vad ca sunt concurenti care au luat AC dupa mai multe incercari, asa ca daca puteti share-ui din testele cu care v-ati debug-at sursa, ar fi super.

Cod:

10
01:21 02:22
00:53 02:03
04:53 05:03
20:17 20:54
20:45 22:11
20:30 21:46
03:11 04:44
01:44 02:06
09:37 10:16
23:46 01:17

Cod:

389

Mersi pentru test. Insa nu vad cum poti obtine 389 pe acest test. Exista doar 2 submultimi de emisiuni care au durata totala egala cu 389 si ambele submultimi contin atat emisiunea 2 (00:53-02:03), cat si emisiunea 10 (23:46-01:17), care se suprapun, deci nu pot fi selectate ambele. Solutia mea gaseste doar o durata egala cu 380, verificata si cu un brute-force, dupa cum am mentionat in primul mesaj. Ai putea sa-mi explici ce emisiuni selectezi pentru a obtine durata totala egala cu 389?

[•UVS_Elfus_Deneo_Kira]

Mda, foarte inspirat sa se observe o greseala fatala dupa 4 ore de concurs.  #mlc

Sunt destul de sigur ca problema se putea rezolva si cu limitele initiale 

Umm, de curiozitate, puteai sa o rezolvi nefiind nevoit sa citesti si sa memorezi toate cele n puncte per test?

[•ssorin_olimpicool]

Sunt destul de sigur ca problema se putea rezolva si cu limitele initiale 

Ne poti spune si cum s-ar rezolva?

[•visanr]

Are cineva niste teste mai "interesante" la problema Talent? Jumatate din timpul de concurs l-am pierdut incercand sa gasesc teste pe care solutia mea nu este corecta, insa nu am reusit. Am scris si un brute sa verific teste generate de mine cu N pana in jur de 20. In clasament vad ca sunt concurenti care au luat AC dupa mai multe incercari, asa ca daca puteti share-ui din testele cu care v-ati debug-at sursa, ar fi super.

Cod:

10
01:21 02:22
00:53 02:03
04:53 05:03
20:17 20:54
20:45 22:11
20:30 21:46
03:11 04:44
01:44 02:06
09:37 10:16
23:46 01:17

Cod:

389

Mersi pentru test. Insa nu vad cum poti obtine 389 pe acest test. Exista doar 2 submultimi de emisiuni care au durata totala egala cu 389 si ambele submultimi contin atat emisiunea 2 (00:53-02:03), cat si emisiunea 10 (23:46-01:17), care se suprapun, deci nu pot fi selectate ambele. Solutia mea gaseste doar o durata egala cu 380, verificata si cu un brute-force, dupa cum am mentionat in primul mesaj. Ai putea sa-mi explici ce emisiuni selectezi pentru a obtine durata totala egala cu 389?

Acele 2 intervale nu se suprapun, deoarece zice in enunt ca "Daca timpul la care se termina emisiunea este mai devreme decat timpul la care incepe, inseamna ca aceasta dureaza peste noapte pana in a doua zi.", asta insemnand ca primul interval este cuprins in intregime in prima zi, iar al doilea este de la ora 23:46 din prima zi pana la ora 01:17 din a doua zi. Sper sa nu zic prostii.

[•mugurelionut]

Are cineva niste teste mai "interesante" la problema Talent? Jumatate din timpul de concurs l-am pierdut incercand sa gasesc teste pe care solutia mea nu este corecta, insa nu am reusit. Am scris si un brute sa verific teste generate de mine cu N pana in jur de 20. In clasament vad ca sunt concurenti care au luat AC dupa mai multe incercari, asa ca daca puteti share-ui din testele cu care v-ati debug-at sursa, ar fi super.

Cod:

10
01:21 02:22
00:53 02:03
04:53 05:03
20:17 20:54
20:45 22:11
20:30 21:46
03:11 04:44
01:44 02:06
09:37 10:16
23:46 01:17

Cod:

389

Mersi pentru test. Insa nu vad cum poti obtine 389 pe acest test. Exista doar 2 submultimi de emisiuni care au durata totala egala cu 389 si ambele submultimi contin atat emisiunea 2 (00:53-02:03), cat si emisiunea 10 (23:46-01:17), care se suprapun, deci nu pot fi selectate ambele. Solutia mea gaseste doar o durata egala cu 380, verificata si cu un brute-force, dupa cum am mentionat in primul mesaj. Ai putea sa-mi explici ce emisiuni selectezi pentru a obtine durata totala egala cu 389?

Acele 2 intervale nu se suprapun, deoarece zice in enunt ca "Daca timpul la care se termina emisiunea este mai devreme decat timpul la care incepe, inseamna ca aceasta dureaza peste noapte pana in a doua zi.", asta insemnand ca primul interval este cuprins in intregime in prima zi, iar al doilea este de la ora 23:46 din prima zi pana la ora 01:17 din a doua zi. Sper sa nu zic prostii.

Undeva pe forumul problemei zice ca emisiunile se repeta in fiecare zi => cele 2 emisiuni se suprapun.

Dar, chiar daca nu s-ar suprapune, daca calculezi durata de timp dintre inceputul emisiunii 2 (00:53 in prima zi) si sfarsitul emisiunii 10 (01:17 a doua zi) o sa vezi ca ai mai mult de 24 ore (si, deci, nu se poate sa vizionezi ambele emisiuni). Iar problema cerea durata totala de vizionare intr-un interval de 24 ore !

[•visanr]

Eu am luat incorect considerand fix 24 de ore in care sa incadrez acele intervale. Nu am gasit niciunde scris in enunt ca emisiunile se repeta si a doua zi (implicit cele 2 intervale nu s-ar suprapune), e problema doar ca se depasesc acele 24 de ore...

[•Vman]

Mda, foarte inspirat sa se observe o greseala fatala dupa 4 ore de concurs.  #mlc

Sunt destul de sigur ca problema se putea rezolva si cu limitele initiale  

Umm, de curiozitate, puteai sa o rezolvi nefiind nevoit sa citesti si sa memorezi toate cele n puncte per test?

Problema se poate rezolva in O(NlogN + logMlogN). Pentru limitele initiale poti tine in memorie jumatate din numere. Sortezi numerele si le afisezi in fisierul de iesire in format binar, apoi faci de maxim logMlogN ori fseek prin fisier  

[•UVS_Elfus_Deneo_Kira]

Genial, ma intreb cati au facut asa....

[•Vman]

Genial, ma intreb cati au facut asa....

Iar eu ma intreb cati au facut doar 10 probleme pentru ca s-au impotmolit la asta??? Ah, nimeni!!!

L.E.: A fost o scapare importanta, de acord, dar de aici pana la #mlc e cale lunga. Ti-as sugera sa iti masori reactiile, pe viitor vei avea numai de pierdut.

[•gobanana]

Aceasta varianta am abordat-o si noi in timp de concurs. Faptul ca exista o solutie si pentru limitele gresite nu cred ca e o scuza foarte buna. In plus, as putea spune ca cei care au rezolvat asa au fost dezavantajati pentru ca au pierdut mult timp pe implementare, fata de cei care au bulanit-o/rezolvat-o dupa anunt.
Pe viitor, la problemele care nu necesita optimizari de memorie ar trebui definita o limita mai mare pentru cantitatea de memorie folosita (32/64MB).

[•mugurelionut]

Eu am luat incorect considerand fix 24 de ore in care sa incadrez acele intervale. Nu am gasit niciunde scris in enunt ca emisiunile se repeta si a doua zi (implicit cele 2 intervale nu s-ar suprapune), e problema doar ca se depasesc acele 24 de ore...

Pai asta e o problema importanta, nu?

In concluzie, testele nu sunt corecte la aceasta problema.

As vrea sa rog autorul problemei "Talent" sa corecteze testele pentru a se potrivi enuntului  Sau macar sa ia in considerare ambele variante ca raspuns corect pentru un test - si cand toate emisiunile se incadreaza in 24h, si cand ar putea depasi 24h. Sunt sigur ca nu sunt singurul care nu s-a gandit ca restrictia de 24h mentionata in enunt era pusa acolo doar pentru a fi, de fapt, complet ignorata in teste.

[•visanr]

Da, este o problema importanta, nu am spus altceva
Si eu am pierdut 30 de minute pe chestia asta + 3 submisii gresite + 4 kb de cod scris degeaba. Din intamplare am reusit sa iau 100 pe ea, ca am zis sa incerc totusi si fara conditia cu 24 de ore, gandindu-ma ca poate am inteles eu gresit ce se cere.  

Imi cer scuze daca s-a inteles altceva din mesajul meu anterior

[•S7012MY]

Mda, foarte inspirat sa se observe o greseala fatala dupa 4 ore de concurs.  #mlc

Sunt destul de sigur ca problema se putea rezolva si cu limitele initiale  

Umm, de curiozitate, puteai sa o rezolvi nefiind nevoit sa citesti si sa memorezi toate cele n puncte per test?

Problema se poate rezolva in O(NlogN + logMlogN). Pentru limitele initiale poti tine in memorie jumatate din numere. Sortezi numerele si le afisezi in fisierul de iesire in format binar, apoi faci de maxim logMlogN ori fseek prin fisier  

Poti sa detaliezi te rog a doua parte( cea cu logMlogN) ?
Multumesc