ONIS 2014 Feedback

[•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  

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

Doua cautari binare. Cauti binar lungimea segmentului, apoi pentru fiecare segment cauti binar ultimul punct care intra pe un segment. nu e chiar logM ma rog.
Totusi, lungimea segmentului este invers proportionala cu numarul de segmente, ceea ce inseamna ca vom in total avea in jur de 2M numere de verificat (daca am aproximat eu bine). Jumatate din ele sunt in memorie, pe celelalte le citim mereu in ordine, deci ar trebui sa se incadreze in timp fara probleme. Bineinteles asta nu e o scuza pentru eroarea din enunt, doar o solutie alternativa interesanta si cu aplicatii in practica

[•mugurelionut]

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

Pai tu ai facut foarte bine ca ai incercat sa trimiti solutia si fara conditia ca toate emisiunile sa se incadreze intr-un interval de 24 ore (asa cum se intelege din enunt). Eu nu m-am gandit la asta. Anyway, ideea este ca asa cum stau lucrurile acum nu este OK dpdv al testelor. Sunt mai multi concurenti care au multe submit-uri la problema "Talent" (fara sa ia AC in cele din urma) si poate ca o parte din ei au solutii corecte conform restrictiilor din enunt.

[•gobanana]

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

Aici scrie ca emisiunile se repeta in fiecare zi: http://www.infoarena.ro/forum/index.php?topic=9710.msg69275#msg69275

In legatura cu testele, si mie mi se pare ca nu sunt conforme cu enuntul.
Daca timpul pierdut de pomana cu debugging-ul nu mai poate fi compensat, macar ar trebui rezolvata problema testelor.

[•S7012MY]

Ma uit pe clasament si vad ca a fost data o reevaluare. Echipa noastra rezolvase initial problema talent si nu mi se pare normal sa se schimbe testele la finalul concursului avand in vedere ca punctarea e de tip acm. Noi am terminat problema cu 2 ore mai repede si sunt destul de sigur ca am fi reparat greseala in concurs daca se schimbau testele.
Probabil o solutie buna ar fi scoaterea problemei din concurs

[•mugurelionut]

Ma uit pe clasament si vad ca a fost data o reevaluare. Echipa noastra rezolvase initial problema talent si nu mi se pare normal sa se schimbe testele la finalul concursului avand in vedere ca punctarea e de tip acm. Noi am terminat problema cu 2 ore mai repede si sunt destul de sigur ca am fi reparat greseala in concurs daca se schimbau testele.
Probabil o solutie buna ar fi scoaterea problemei din concurs

Vad si eu acum ca s-a reevaluat problema "Talent". Din pacate asta nu e OK pt cei care in timpul concursului au rezolvat-o ignorand conditia de 24h (fara sa aiba vreun submit in timpul concursului care sa tina, totusi, cont de acea conditie). Eu sunt de parere ca ar trebui scris un mic evaluator care sa considere ambele raspunsuri corecte pentru aceasta problema (ca sa nu fie dezavantajati nici cei care au luat AC in timpul concursului, dar nici cei care nu au luat, dar au rezolvat problema corect conform tuturor restrictiilor din enunt). Sau, eventual, sa fie scoasa din concurs asa cum ati propus si voi.

[•DraStiK]

O sa se ia 100 pe talent si cu abordarea veche si cu cea noua. Stati linistiti!

[•wefgef]

Organizatorii ONIS poarta discutii pe marginea acetui subiect. Pana vom lua o decizie problema Talent va fi scoasa din concurs.

[•Cristy94]

Felicitari pentru runda, unele probleme au fost chiar frumoase

O sugestie ar fi (cum a mai scris cineva mai sus) sa nu se ia submisie gresita pentru eroare de compilare. Noi am trimis o sursa in care foloseam sort(..., cmp) iar in functia de cmp aveam cmp(int &a, int &b). La mine nu zicea nimic, pe infoarena a dat eroare de compilare, parametrii trebuind sa fie si "const".


Clasamentul general cum se calculeaza si cand se actualizeaza?
Cate echipe se califica mai departe?

PS: Am trimis din gresala o submisie de pe contul meu in loc de cel al echipei, sper ca nu are nimic  

[•geniucos]

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

Doua cautari binare. Cauti binar lungimea segmentului, apoi pentru fiecare segment cauti binar ultimul punct care intra pe un segment. nu e chiar logM ma rog.
Totusi, lungimea segmentului este invers proportionala cu numarul de segmente, ceea ce inseamna ca vom in total avea in jur de 2M numere de verificat (daca am aproximat eu bine). Jumatate din ele sunt in memorie, pe celelalte le citim mereu in ordine, deci ar trebui sa se incadreze in timp fara probleme. Bineinteles asta nu e o scuza pentru eroarea din enunt, doar o solutie alternativa interesanta si cu aplicatii in practica

Nu cumva era " O(NlogN + MlogMlogN) "? Eu am facut-o initial ca sa imi intre in memorie cu O(Nlog^2N+NlogClogN) ca timp.Tineam un vector de int cu pozitiile numerelor in ordinea crescatoare a acestora.Ca sa aflu eficient valoarea de pe o pozitie faceam cu ridicare de matrci la putere in timp logaritmic in logN si, de asemenea, cautam binar rezultatul. 

[•wefgef]

Am decis sa renuntam la problema Talent, clasamentul va fi facut ignorand toate submisiile si punctajele de penalizare obtinute.

Momentan avem o problema cu afisarea clasamentului, acesta fiind un tip nou de concurs organizat pe infoarena. Pana acum nu ne-am mai confruntat cu o asemenea situatie, vom lucra la afisarea corecta a clasamentului in decursul acestei saptamani. Am fi vrut sa gasim o solutie de compromis, alternativele fiind:

• Sa admitem ca fiind corecte ambele rezolvari. Astfel am fi avut o problema cu raspuns unic la care surse care dau raspunsuri diferite ar fi trecut testele.
• Sa consideram corecte doar acele surse care respecta toate restrictiile din enunt.
• Sa consideram corecte doar acele surse care au luat AC in concurs. Acest lucru ar fi insemnat ca una din restrictiile enuntului sa fie ignorata.

Din pacate niciuna din cele 3 alternative nu a reusit sa multumeasca toti organizatorii, asa ca suntem nevoiti sa retragem problema.

Ne cerem scuze pentru neplacerile create si va multumim ca ati participat la ONIS 2014! Va asteptam in continuare si la celelalte concursuri organizate de infoarena!

[•Teodor94]

Problemele au fost adaugate in arhiva. Pagina solutiilor este in curs de editare. Spor la citit si la codat!

[•S7012MY]

Ar merge sa stergeti linkul catre clasament de pe homepage ca din cate vad eu nu e final 

[•Cristy94]

De ce nu mai se poate vizualiza clasamentul? http://www.infoarena.ro/onis-2014/clasament/runda-3

[•wefgef]

Il vom face public dupa ce vom implementa modelul corect de afisare a rezultatelor.

[•geniucos]

Cam cand o sa fie vizibil clasamentul? A trecut aproape o saptamana...

[•Andrei1998]

Cum spunea si Costin Oncescu, au trecut deja 10 zile de la runda, asteptam cu totii cu nerabdare update-ul de rating. 

[•ciprianf]

Runda 4 (27 aprilie) nu se suprapune cu etapa pe Bucuresti a ACM-ului?

[•gabriel.badea]

Pe site-ul oficial scrie ca pe 26 aprilie va avea loc faza locala la ACM.

[•ciprianf]

Care este site-ul oficial pe care ai gasit anuntul? Noi (la fac de Automatica si Calculatoare Bucuresti) am fost anuntati ca este duminica, 27 aprilie. In general ACM-ul este duminica, nu sambata.

@Echipa Infoarena: Voi ce stiti?

[•maritim]

Din cate stiu eu runda 4 de ONIS va fi in acelasi timp si runda de ACM faza pe Bucuresti.

[•gabriel.badea]

Nu este un pic cam mult sa fie organizate 2 concursuri de 5 ore in zile consecutive ? Rolul ONIS-ului a fost sa fie ca o pregatire pentru ACM. Credeti ca dupa 5 ore sambata se poate concura la acelasi nivel si duminica ?

[•PlayLikeNeverB4]

Nu toata lumea participa la acelasi set de concursuri.

[•gabriel.badea]

Normal ca nu toata lumea participa la acelasi set, dar cei pentru care sunt organizate aceste concursuri in special(studentii) participa. Deci aceasta a fost ideea cu zilele consecutive ? Fiecare sa isi aleaga setul "preferat"?

[•Teodor94]

Dupa un mic delay, am adaugat problemele in arhiva! Vom publica si pagina cu solutii in curand.

[•Vman]

Am publicat articolul cu solutii pentru runda 4: http://www.infoarena.ro/onis-2014/solutii-runda-4.
Va invitam sa studiati solutiile, sa le discutati, completati si implementati  

Din pacate am depistat o gresala in generatorul de teste pentru problema Cercuri5   Vom reface testele si vom reevalua. Imi cer scuze pentru neplacerile create.

L.E. Am reevaluat problema Cercuri5. Felicitari echipelor UAIC Balan Negrus Hreapca, UVS Omer Darius Casi, TUCN Eagles si lui Rares Buhai care au reusit sa o rezolve corect!