infoarena

Concursul FMI No Stress 5 (http://www.infoarena.ro/fmi-no-stress-5) s-a încheiat! Felicitari tuturor participantilor!

Asteptam impresiile voastre legate de concurs!

Dupa ce am terminat concursul ma gandeam ca mai bine dormeam mai mult de dimineata / dadeam Codeforces-ul de ieri. Insa acum ca m-am mai linistit dupa maratonul de implementare o sa incerc sa fac o analiza cat de cat obiectiva.

In afara de problema Something care chiar mi-a placut, si intr-o oarecare masura de problemele Mere si Noname2, restul problemelor mi s-au parut ca respecta ecuatia (problema = idee relativ simpla + cat mai multe chichite de implementare) fapt care personal nu imi place foarte mult.

Cateva impresii, foarte scurte, despre probleme, in ordinea in care le-am facut (SEMI-SPOILERS AHEAD)

• Taste: O problema ok de manipulari pe biti / mate, iar detaliile de implementare nu sunt foarte pregnante (dar long-long-ul mi s-a parut inutil)
• TDeque: O problema doar de implementare; pornind destul de obosit concursul, am citit ca se accepta oricare solutie, nu doar cea minima. Dupa ce mi-am dat seama de ce iau 50, conversia a fost usoara.
• Patrate6: Ok sa comprimi 4 patrate egale intr-unul de latura dubla; not ok sa trebuiasca sa tii doar cele mai mari 10^6 laturi (cred ca mergea si mai putin, atat am tinut eu).
• Mere: Fiind cu moralul destul de jos dupa primele 3 probleme, asta mi-a adus un zambet, care a tinut chiar si dupa unul-doua cazuri particulare de descoperit (care in mod normal nu imi plac). Personajele puteau fi numite altfel pentru a nu da un hint cu privire la posibilele rezultate ale jocului, dar pana la urma asta a adus zambetul :D
• Something: Prima idee: iau doar o muchie compusa din doua noduri non-critice si o colorez in doua culori diferite de cea majoritara. Dupa 40 de minute si multe "Da' acuma de ce iau 50?" retorice, mi-am dat seama ca poate nu e strategia buna after all. GG autorului, de departe cea mai buna problema din concurs.
• Noname2: Cautare binara si sume partiale. O problema ok. Also, prima care mi-a iesit din prima submisie...
• Algebra2 sau cum sa inghesuim cat mai multa algebra modulara intr-o singura problema...
• Criptare2: Am evitat-o la inceput, dar n-a fost asa rea - ideea se bazeaza pe gasirea unei forme comune a stringurilor care pot avea aceeasi criptare. Am descoperit din nou cat de inceata e citirea cu streamuri... (niciun avertisment din partea autorului privind asta)
• Grid: Cand suntem in pana de idei, dam treapuri? (serios acum, se poate face si altfel?)

Stiu ca acest concurs a fost conceput pentru cei care sunt mai la inceput de drum cu agloritmica, insa multe din probleme nu mi s-au parut ca dadeau vreo urma de satisfactie la gasirea ideii (care de multe ori nu era bine ascunsa). In schimb, am codat cam 4 ore din 5 la concursul asta...

Mulțumim de feedbackul detaliat , Vlad!

În legătură cu problema criptare, pe sursa oficiala citirea se făcea  cu stream-uri și am avut timpi de aproximativ 200ms, folosind unordered map din stl fără "smenuri" pe lângă.

Cu placere :)

Am scris acea remarca pentru ca la un moment dat am trimis doar citirea (e drept ca si cu o afisare inutila) si ajungea la 450ms. http://www.infoarena.ro/job_detail/1272494?action=view-source

Stiu ca limita e pusa incat sa intre lejer o sursa cu orice fel de citire, insa se obisnuia ca la problemele cu output mare sa se specifice ceva de genul "Recomandam citirea cu fgets". As zice ca la orice problema la care operatiile de input / output iau mult timp sa se specifice ceva de genul: "Atentie, citirea neparsata ocupa un procentaj semnificativ din timpul de rulare al solutiei oficiale".

Multumim pentru feedback!  :)

Cred că pentru concurenții începători problemele au fost mai interesante. E adevărat că au existat cam multe chichițe de implementare, care nu aveau neaparat legătură cu problema. Se va lucra la asta :).

Da, toate soluțiile oficiale la Grid sunt în O(sqrt(n)) și sunt destul de elementare ca idee (iese elegant cu câte un deque per bucată spre exemplu). Am evitat intenționat să dăm mai multe puncte pentru treapuri, pentru a încuraja aceste soluții.

Mi-a placut in special problema patrate6, era putin pe baza ideii de la huffman trees (cea in care nu primesti costurile in ordine), mi-a iesit din prima cu un priority queue.
Mi-a mai placut mult problema something, ideea de dfs din cele 3 noduri.
M-am chinuit foarte mult la algebra2 sa-mi dau seama de ce iau doar 70 de puncte si inca n-am reusit, inca am impresia ca depasesc undeva domeniul (pentru ca primesc incorect), insa nu realizez unde.
Ma urasc, am vrut sa invat skiplist cu 2 zile inainte de concurs, am zis ca las pe dupa, mi-ar fi fost foarte utile.
Nu inteleg de ce s-a pus atat de mult accent pe reprezentarea numerelor pe 64 de biti, mi se pare c-ar fi fost suficient la o problema pentru a testa asta, nu la 3 (parca 3 erau).
Thank you for the name of the emperor (@Taste).

Am fost putin dezamagit de organizare totusi, ma asteptam la ceva pregatit putin dinainte, in loc de replica domnului Dumitran "am fost in laboratorul asta cu o grupa acum cateva zile si mergeau". Nu zic ca trebuia ceva ca la ONI, in care fiecare sa fim repartizati la un anumit calculator, dar as fi vrut sa se stie dinainte ca sunt suficiente (si, desigur, care) calculatoare functionale, cu acces la internet, codeblocks/mingw instalat s.a.


Edit: Am gasit solutia la Algebra2, my bad again.

@ Vlad Gavrila: Multumim, evident, pentru feedback :) , dar nu sunt de acord cu unele din remarcile tale.

Eu cred ca chichitele de implementare isi au locul lor intr-un concurs de info. Ca programator, daca ai de a face cu chichitele astea aici, o sa ai cu atat mai putine bug-uri si cu atat mai mult insight cand o sa programezi la nivel inalt. Ideea cu marirea limitelor patratelor la Patrate6 a fost, spre exemplu, a mea, si imi asum raspunderea daca unora nu le-a placut :P. Personal, mi se pare important ca daca cineva trage de limite (cum se intampla la interviuri de coding si chiar cand elaborezi un proiect)  tu sa stii inca sa implementezi problema iar aici mi s-a parut, in particular, interesant (se putea face in mai multe moduri) . Stiu ca ar fi fost frumos ca patratele sa-ti fie date sortate si pana in 10^6, gata gata sa-ti aplici algoritmul pe ele.

La fel si cu long long-ul la Taste. Aici am cazut de comun acord in comisie. Vroiam ca cei care au fost blocati in concurs de chestia asta, dupa ce mai stau putin pe probleme acasa, sa poata la alte concursuri sa jongleze usor cu long long acolo unde e nevoie.

Btw, la algebra2 nu prea e algebra modulara. Poate doar sa stii ca daca vrei sa calculezi o expresie mod n, exponentul trebuie calculat mod fi(n). Dar nu e nici chestia asta necesara, se putea rezolva exponentiind pe rand, de doua ori.

Din nou, multumim pentru feedback :)

@Vlad (si pentru oricine e interesat de ce uneori citirea cu streamuri e mai inceata). Acolo ai tu o greseala de implementare, destul de mare defapt.

Deschizi cu freopen si citesti cu streamuri. In versiunile recente de C++ s-a hotarat sa se sincronizeze cin cu scanf,  ca sa le poti folosi alternativ fara sa se comporte dubios, din cauza bufferurilor. Asta le face muuuult mai incete. Daca vrei sa citesti de la stdin cu streamuri (sau de la stdin care duce spre un fisier din cauza lui freopen) e bine sa folosesti ios::sync_with_stdio(false); (http://www.cplusplus.com/reference/ios/ios_base/sync_with_stdio/), sau chiar mai simplu fstreams. (ifstream si ofstream). Overall streamurile sunt mai rapide (la afisare sunt cu 5% mai incete decat printf) asa ca vi le recomand tuturor.

@Mihai Nitu:

Nu am spus ca e bine ca problemele sa nu aiba deloc chichite de implementare - sunt de acord cu tine ca fac parte din concurs si sunt importante pentru a invata cum sa eviti buguri. Ce nu mi-a placut a fost ca dificultatea concursului a fost data in special de astfel de chichite, si nu de ideile din spatele problemelor. Daca vedem concursul asta ca pe unul de antrenament pentru implementare, atunci putem spune ca si-a atins scopul.

@Adrian Budau:

Bine de stiut, merci! :D

Am o nedumerire : clasamentul va fi facut public ?  ???

@xtreme77 Clasamentul va fi public dupa premierea de la FMI din seara asta

Am inteles,multumesc frumos ! :D

Se mai posteaza solutiile?...a trecut ceva timp...