infoarena

Prima rundă a concursului ONIS 2014 (http://www.infoarena.ro/onis-2014) s-a încheiat. Felicitări câștigătorilor (http://www.infoarena.ro/onis-2014/clasament/runda-1)!

Vă rugăm să postați aici impresii și sugestii legate de această rundă.

Mi-au placut subiectele. Cam mici limitele de timp si memorie la unele probleme si cam mari la altele, dar per total a fost ok. Astept urmatoarele runde.  :D

Foarte buna ideea, chiar era nevoie de un astfel de concurs de pregatire pentru ACM :)
Frumoase problemele, sa creati si pagina cu solutii. ( http://www.infoarena.ro/onis-2014/solutii-runda-1 )

Pagina cu solutii este in lucru :D . Va fi gata cat mai curand.

De ce nu este public clasamentul?

Clasamentul este public.

Este public. http://www.infoarena.ro/onis-2014/clasament/runda-2 (http://www.infoarena.ro/onis-2014/clasament/runda-2)

Runda s-a incheiat! Problemele vor fi adaugate in arhiva in cel mai scurt timp.

Felicitari tuturor participantilor!  =D>

Super problemele !  =D> Mi-au placut mult progr si progr2 pentru ca am reusit sa le facem relativ rapid, in ciuda faptului ca multi buseau la ele :rotfl: .

cand se afisaza clasamentul general?

Ati avut niste probleme foarte frumoase la runda 2 si mi-a facut placere sa ma gandesc cum se rezolva in timpul concursului. Si ma bucur ca olimpiada a avut succes si din punct de vedere al numarului de echipe participante (eu am numarat aproape 70 echipe - considerand doar user-ii care aveau o abreviere de universitate sau numele mai multor persoane in nume/username). Dar mi se pare ca au fost prea multe echipe care nu au reusit sa rezolve nicio problema, asa ca sugestia mea ar fi ca la rundele viitoare sa aveti 1-2 probleme in mod evident simple (la care solutia sa fie foarte usor de implementat, evidenta si "pe fata"). Uitandu-ma pe clasament, pare ca problemele cele mai rezolvate au fost "Baruri" si "Pufarina" (sper sa nu gresesc - nu am facut o numarare exacta). Dar n-as incadra niciuna din aceste 2 probleme in categoria de "evident simpla". La "Baruri" e nevoie de o structura de date pentru sume pe interval si actualizari "punctuale". "Pufarina" e, intr-adevar, foarte simpla ca implementare, dar e un pic neobisnuita (trebuie sa gandesti un pic ca sa iti dai seama care-i treaba). Eu as sugera ca macar una din probleme sa fie aproape "brainless" (rezolvarea a astfel de probleme, chiar daca foarte simple, ajuta la moralul echipelor participante).

In incheiere, felicitari pentru o runda foarte buna atat dpdv organizatoric, cat si si stiintific!

Multumim pentru sugestie. Sunt de acord si o sa se tina cont de ea.

Foarte frumoase problemele :D , feilicitari organizatorilor!

De ce la Baruri nu intra in timp cu Arbori de Intervale? :( http://www.infoarena.ro/job_detail/1080590?action=view-source
Nu era normal sa intre si aceasta solutie in timp? :D Adica nu am mai intalnit pana acum probleme care sa intre in timp cu AIB si nu cu arbori de intervale :(

Era normal sa intre, s-a intamplat sa nu intre :D.

Imi poate spune si mie cineva ideea din spatele problemei Facebook Search? Eu am incercat cu trie, dar nu mi-a intrat in memorie. :)

Cu trie se face, probabil ai o problema la implementare.

Poti fi mai explicit, te rog?
Ce ar trebui sa retin in fiecare nod al trie-ului?

L.E Ar putea fi o problema recursivitatea?

Recursiv am facut si eu, iar in fiecare nod din trie retin adresele celor 26 de fii, plus un int.

Eu am facut cu arbore de intervale si n-am avut probleme cu memoria.

Salut! Mie mi-a intrat baruri cu 450 ms. ( folosind arbore de intervale)

Felicitari pentru runda!

Cand se afiseaza clasamentul general pe cele 2 runde ? :) si solutiile la a doua runda ? :D

In testele de la problema Progr2 (http://www.infoarena.ro/problema/progr2) nu a fost respectata restrictia din enunt Numerele lui Georgică sunt distincte. De aceea, sursele din concurs vor fi reevaluate.

Acum se lucreaza la pagina cu solutii, va rugam sa aveti rabdare.

Salut . Imi poate spune cineva care e solutia la X si 0 ?

Nu se afiseaza si clasamentul general pe cele doua runde ?

Multumesc  8)

Algoritmul Minimax + memoizare.

Cand o sa fie runda 3?

O sa fie anuntata in curand pe pagina principala.

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 :D

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.

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

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

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

389

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

ce gresala denis?

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

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

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?

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

Ne poti spune si cum s-ar rezolva?

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 !

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

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  :banana:

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.

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

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.

Da, este o problema importanta, nu am spus altceva :D
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.  [-X

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

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

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.

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.

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.

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

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

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  :oops:

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

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!

Problemele au fost adaugate in arhiva. Pagina solutiilor (http://www.infoarena.ro/onis-2014/solutii-runda-3) este in curs de editare. Spor la citit si la codat! :D

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

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

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

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

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

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

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

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?

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

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 ?

Nu toata lumea participa la acelasi set de concursuri.

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"?

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

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

Din pacate am depistat o gresala in generatorul de teste pentru problema Cercuri5  :aha: 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!

Mi se pare doar mie sau ati updatat ratingurile la runda 4 si nu le-ati updatat la runda 3? :rotfl:

La runda 3 au existat niste probleme organizatorice (in cazul a doua probleme erorile din enunt au fost corectate cam tarziu), motiv pentru care am decis sa nu o luam in calcul pentru rating.

Am confirmat participarea echipei pe mail la adresa mentionata insa nu a raspuns nimeni. S-a primit email-ul?

Da, mail-ul s-a primit. Am raspuns la toate confirmarile cu o confirmare de primire. Teoretic, ar fi trebuit sa o primiti.

Exista undeva pe aici programul ONIS 2014? Sunt doar curios daca se asteapta pentru a se afisa la premiere clasamentul final sau nu. Oricum, o runda frumoasa. Acelasi lucru pot sa spun si despre ACM Faza Nationala 2014 de ieri. Felicitari.  :thumbup:

Foarte adevarat!Frumoasa runda!Felicitari tuturor!  :D

P.S:Un hint despre ora la care se vor afla rezultatele finale?  :-'

Clasamentul a fost ascuns pana dupa premiere. Ar trebui sa fie vizibil acum  :)

Am adaugat problemele in arhiva. Distractie placuta! :D

Dupa cum am sugerat si in timpul probei de mai multe ori, testele la problema Similar nu respecta restrictiile din enunt (exista unele siruri vide).

Acum ca sa fie totul frumos pana la capat, ati putea da si update la rating pentru runda de ieri. ;) La cea de azi va trebui cu siguranta mai intai recorectata problema similar. Multumim pentru runde.  :thumbup:

Probleme mult prea usoare.

Imi puteti explica si mie va rog de ce o sursa care citea cu gets[1] la problema similar lua 0 iar una care citea cu cin[2] lua 100 ? Sunt linii goale in fisier ?

[1] http://www.infoarena.ro/job_detail/1187796?action=view-source
[2] http://www.infoarena.ro/job_detail/1188195?action=view-source

Puteti adauga solutiile la probleme: http://www.infoarena.ro/onis-2014/solutii-runda-finala

Din cate vad eu problema 'similar' a fost re-evaluata, din pacate nu ne-am dat seama de asta in timpul concursului. (desi am verificat).
Pare ca doar o echipa eligibila a rezolvat-o dupa evaluare, asa ca premiile nu au fost afectate (prima solutie accepted din concurs a ramas accepted si dupa).
Desigur, alte implicatii din concurs nu pot fi reparate acum, ne cerem scuze pentru neplacerile cauzate.

Cand se da update la rating? Nu cred ca e nevoie ca dupa fiecare runda sa asteptam cel putin o saptamana pentru a se updata ratingurile (de data asta inca nu e o saptamana, dar mai e putin si se face) :) Daca nu s-ar intarzia de fiecare data update-ul, nu ar mai aparea postari de genul asta :roll:

Problema Bacterii2 are o parte din teste gresite, banuiesc ca e din cauza preciziei, am bagat o sursa cu calcule pe double care intra http://www.infoarena.ro/job_detail/1188625 si una fara testata cu brute care ia incorect http://www.infoarena.ro/job_detail/1189445, ar fi frumos daca ar putea testa cineva.

Am verificat testele si iti pot garanta ca sunt ok. O singura linie din output este diferita fata de rezultatul tau, iar raspunsul tau nu este corect (am verificat manual, fiind chiar un rezultat cu R = 2 = 1+1). Posibil sa ai un overflow undeva...

L.E. am mai sapat putin prin sursa ta si am ajuns la concluzia ca "rezultatul tau = rezultatul meu % modulo". Ai grija la cat de mare poate fi raspunsul.

Da,  testele sunt bune am incercat cu modulo mai mare si merge, raspunsul putea fi mai mare.

Pentru runda finala se vor mai updata ratingurile sau nu se va mai tine cont de ultima runda?   :-'