infoarena

Runda 2 (http://infoarena.ro/algoritmiada-2012/runda-2) a concursului Algoritmiada 2012 (http://infoarena.ro/algoritmiada-2012) s-a încheiat. Felicitări primilor clasați (http://infoarena.ro/algoritmiada-2012/runda-2/clasament/5-9)!

Așteptăm opiniile și eventualele sugestii ale concurenților în legătură cu oraganizarea, subiectele propuse și orice probleme întâmpinate.

Mult succes în continuare!

A fost un concurs frumos, cu probleme interesante (abia astept sa citesc descrierea solutiei la kgraf, caci ce am eu, desi polinomial, depaseste cu mult timpul de executie :) ).

De asemenea, mi se pare ca ati facut o treaba foarte buna cu doar 5 probleme distincte (la toate grupele). Eu cred ca ar fi bine daca ati mentine aceasta situatie si pe viitor, din urmatoarele motive:
1) probleme mai putine per runda inseamna mai putina munca pt echipa infoarena sau inseamna ca problemele pregatite pot fi testate mai bine, eventual de mai multe persoane (si stiti cat de mult e de munca cu pregatirea serioasa a unei probleme)
2) probleme mai putine per runda inseamna ca aceeasi problema ajunge la mai multe grupe de varsta si sunt mai multi oameni care vor incerca sa o rezolve ; in plus, apare si o mini-posibilitate de a compara (cel putin partial) capabilitatile concurentilor din grupe diferite (chiar daca nu in mod "oficial")

Dragute problemele - si parca putin mai usoare decat la runda precedenta. Felicitari tuturor!
Cateva observatii as vrea sa fac totusi:
Ar putea sa se strecoare in enunturile problemelor, la fel cum se facea mai demult, si unele definitii:
De exemplu la problemele de azi se putea introduce definitia pentru subsecventa, subsir, lant ...
Am gasit definitii ale lantului care ziceau ca ordinea muchiilor nu conteaza si atunci cred ca era alt raspuns pe exemplu la problema kgraf.
Definitia era asa: un lant e o secventa de muchii u1, u2, ..., uk cu proprietatea ca ui si u(i+1) sunt arce incidente (orientarea nu conteaza).

Cateva observatii/sfaturi legate de codare:
1.Daca avem:
set <int> s;
s.upper_bound(2) e O (logn), pe cand upper_bound (s.begin(), s.end (), 2) e O (n)
2.Nu schimbati niciodata chestii in ultimele minute si resubmitati - eu asa am pierdut 85 de puncte la SecvMin

Edit:
Am gasit de ce erau 85 si nu 100 de puncte. In loc sa iau lungimea minima dintre toate lungimile subsecventelor "stranse" care contineau sirul respectiv ca subsir, luam lungimea ultimei subsecvente. Ceea ce inseamna ca pe 17 din 20 de teste raspunsul era dat chiar de ultima potrivire a lui b in a si daca porneai cu potrivirea de la sfarsit la inceput luai 85 chiar daca faceai destul de prost. Poate ar trebui revizuite testele. Sau macar pe viitor sa incercati sa nu puneti ultima solutie gasita cu back din spatiul de solutii, chiar daca vreti sa scoateti cu TLE solutiile slabe.(ci penultima :-')

Mi-au placut problemele :D. Insa de ce nu se modifica ratingul?
Nu imi recunoaste concursul deloc

Rabdare...

Ontopic:

O runda foarte interesanta. Mi-au placut problemele. D-abia astept sa fac solutia oficiala la problema kgraf :D

In schimb a fost destul de nasol cu evaluarea surselor in ultimele 5 minute... Am preferat sa nu mai trimit nicio sursa decat sa risc sa pierd punctele.

Ultimul sfert de ora chiar, dar asta e. Nu prea ai ce sa faci, cand se trimit atatea bruturi la probl cu 2s pe test.

Runda foarte misto, felicitari organizatorilor. Kgraf se vede din enunt ca e ceva nou, which is great  :).

Felicitari tuturor participantilor! Ne pare rau pentru evaluarea tarzie, speram ca nu v-am incurcat foarte tare... Ratingurile probabil ca se vor modifica in curand, Wefgef se ocupa de asta. Inca odata, felicitari si va asteptam si la Runda 3!

Au fost updatate si ratingurile!

@mugurel Uite cum m-am gandit la kgraf. Valoarea unde ai adunat costurile a k muchii din un drum si ai scazut costurile a altor k muchii din acelasi drum se maximizeaza atunci cand faci diferenta intre k muchii de valoare maxima si k muchii de valoare minima. Astfel pt fiecare nod tii minte k^2 valori, best[nod][i ][j] o sa fie drumul ce se termina in nod pentru care valoarea in care am adaugat costu a i muchii si am scazut costul altor j muchii e maxima. Fiecare muchie e procesata de k^2 ori deci algoritmul o sa aiba complexitate O(k^2 m).

Scuzati-ma ca intervin.. @Cosmin.. asta ar fi in total O(K*M^3). dar asta cred ca merge doar pentru N mic!?

nu e kM^3

fiecare arc a->b il folosesti pentru a actualiza k^2 stari pentru nodul b, cum ai m arce timpul total e m * k^2.

Cand vor aparea solutiile la problemele date la runda a II-a ?
Sunt curios sa vad cum se rezolva problemele :weightlift:

A fost creata pagina http://infoarena.ro/algoritmiada-2012/runda-2/solutii (http://infoarena.ro/algoritmiada-2012/runda-2/solutii) , doar ca momentan a fost completata solutia numai la problema Triplet.

Am o solutie de 40 puncte la secvmin si una de 40 puncte la planificare.
Am observat ca la  triplet e explicata solutia pe categorii de punctaj: solutie de 40pct si solutie de 100pct...
Nu as putea ajuta la solutiile de 40 de la secvmin si planificare? :-'