Nu

Da, nu conteaza in ce ordine sunt elementele din sir.

Da

Da

Da

Fara comentarii

Da

@Vlad
La problema 1 nu cred ca ai inteles bine. Daca ai cazul urmator: un nod conectat la 10 fii si costul dintre nod si oricare fiu e 10, iar ce ai cautat tu binar e 15, trebuie sa eliminii pe rand toti fiii, nu doar pe cel mai mare. Pentru asta cam trebuie sa sortezi descrescator fiii pentru un nod si dupa sa vezi primii doi care au suma mai mica sau egala cu ce ai cautat tu. Complexitatea iti iese cam O(N log N log Cmax) si nu era destul de buna. Cu mai multe optimizari am reusit sa am 1.2 secunde, dar limita era o secunda.
La problema 3 se poate o dinamica d[n][j][k] = in cate moduri poti sa pui n numere daca al doilea poate sa aleaga numere din cele mai mici j si al treilea poate sa aleaga din cele mai mici k, n >= j >= k. Exista recurenta destul de usoara in O(N), dar se poate reduce cu sume partiale la O(1). Daca folosesti numere mari cu baza 10^9 intra destul de lejer in timp si O(N^4 * nr_mari) pentru ca ai constanta foarte mica.

Anul asta la IOI nu s-au confiscat telefoanele inainte de probe. Singura masura a fost inchiderea internetului in hotel. Inainte de a doua proba am vazut vreo 2 turci care stateau pe net pe telefoane, deci nici asta nu a fost o mare problema daca incercai sa "socializezi".

Pe total, Andrei e pe 1 , Rares pe 3 , Alex pe 6 si Radu pe 13  .

Problema 3 suna cam asa:

Trebuie sa faci un Encode si un Decode. Encode primeste doua numere X si Y, X != Y si trebuie sa returneze un numar H. Decode primeste un numar Q si numarul H returnat de Encode si daca Q = X trebuie sa returneze 1, altfel 0, Q e tot timpul fie X fie Y.

Restrictii: 1 <= X, Y <= 920
Pentru 27 de puncte 1 <= H <= 20
Pentru 100 de puncte 1 <= H <= 12
Intr-un fisier sunt 2 milioane de testcase-uri.

La clasa a IX-a solutia oficiala la problema "progresie":http://oni2014.cnlodobescu.ro/wp-content/uploads/2014/04/progresie.pdf este gresita. Desi sunt vreo 3 solutii oficiale de 100 de puncte, niciuna nu este corecta. In enunt zice ca elementul maxim sa fie <= [2 * N * sqrt(N)] dar comisia nu respecta asta. Pentru n = 4097 toate cele 3 solutii oficiale afiseaza cel putin un numar > 530.000, dar [2 * 4097 * sqrt (4097)] = 524.480.
Din cate stiu, au fost 2-3 concurenti care au gasit o alta solutie care se incadreaza in limitele problemei, dau au fost inca vreo 4 care au avut solutia proasta a comisiei. Toti 6-7 au luat 100 de puncte. Astazi la intalnirea cu lotul cand am ridicat problema asta au zis ca solutia lor e buna si ca nu am inteles eu, dar acum m-am uitat pe sursele oficiale si sunt proaste. Ce trebuie facut intr-un astfel de caz?

Aici sunt sursele oficiale. Sunt mai multe teste pe care solutiile dau gresit, dar nu am stat sa le caut pe toate. Inca cateva exemple sunt 4098 si 4099.
https://ideone.com/Sh2nmm - Chesca Ciprian (am comentat ifstream si ofstream si am inlocuit f>> cu cin>> si g<< cu cout<<)
https://ideone.com/tt07k6 - Pit Rada Vasile Ionel (am adaugat iostream, am comentat fin si fout si am inlocuit fin>> cu cin>> si fout<< cu cout<<)
https://ideone.com/yyCXsd - Eugen Nodea (singurele modificari au fost sa comentez freopen-ul)

Singura sursa oficiala care respecta restrictia ca numerele sa fie mai mici decat 2 * N * sqrt (N), pacat ca nu respecta si restrictia ca numerele sa nu fie in progresie aritmetica (un exemplu 88574 177148 265722)
https://ideone.com/qDHMIc - Popescu Silviu (am scos freopen-ul)

Citeste bine enuntul si intelege-l. In momentul in care ai primul query celelalte operatii inca nu s-au executat inca(inca nu s-a aduagat niciun insert, nu s-a adaugat niciun delete, etc).

Cum te uiti pe axa timpului inainte de prima operatie nu exista nici un insert sau erase. Deci nu exista nicio valoare.

Nu se precizeaza nicaieri ca operatia de tipul 5 se adauga la un moment de timp, la ea trebuie sa raspundeti pe loc in functie de cum arata axa timpului.

Nu vor exista doua operatii de insert cu aceeasi valoare in acelasi timp.

Fara comentarii.

Da.

Da.

NO COMMENT

Apare următorul mesaj la o problemă (http://www.infoarena.ro/problema/algsort) : „Eroare în configurarea problemei”. Ce este de făcut?

Fixed.

Comisia a hotarat sa se mareasca limita de timp cu 0.1 sec. Am dat un reeval si totul este ok acum.

Aici puteţi discuta despre problema Luff.

Aici puteţi discuta despre problema Ksecv3.

Aici puteţi discuta despre problema Arbpal.

Aici puteţi discuta despre problema Aby.