infoarena

Runda 2 (http://infoarena.ro/algoritmiada-2011/runda-2) a concursului Algoritmiada 2011 (http://infoarena.ro/algoritmiada-2011) s-a încheiat. Felicitări primilor clasați (http://infoarena.ro/algoritmiada-2011/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!

Cand apar solutiile problemelor ?

merge drumuri3 mai bine de O(n ^ 3 log K) ?

La Drumuri3 trebuia parsata citirea?...  :-k

ce complexitate ai scos?

Preprocesare cum ai scris mai sus, si O(1) pe query dupa.

Eu am luat 100 asa, nu am avut probleme.

Nu prea ai ce sa parsezi la drumuri3 fiindca mai mult de n ^ 2 + q linii nu pot fi. Oricum , am impresia ca gruparea testelor la drumuri3 nu e chiar foarte fericita, cred ca sunt cateva surse O(N ^3 log K) care iau putine puncte.

Felicitari echipei pentru o runda faina. Si site-ul s-a comportat mai bine comparativ cu alte concursuri recente =D>

Dar cum faceati preprocesarea la drumuri3?
Eu m-am gandit asa:
Daca numim M matricea de adiacenta a grafului, si luam B=M+M^2+...+M^(k-1), atunci
B_(i,j) e nr de drumuri intre i si j. Acuma B=(M^k-M)/(M-I). Asta se poate calcula in O(n^3logk), dar nu stiam daca M-I e inversabila tot timpul.

Acuma intrebare: E M-I inversabila tot timpul, sau aveti alta metoda de calcul?

Pai o chestie de care eu mi-am dat seama cam tarziu ar fi urmatoarea :
A ^ 1 + A ^ 2 + A ^ 3 + A ^ 4 + A ^ 5 + A ^ 6 + A ^ 7 + A ^ 8 =
         A ^ 1 + A ^ 2 + A  ^ 3 + A ^ 4 +
A^4 (A ^ 1 + A ^ 2  + A ^ 3  + A ^ 4) =

( A ^ 4 + I(n)) ( A ^ 1 + A ^ 2 + A ^ 3 + A ^ 4). Si tot asa :) Ajungi la un produs de logK factori.

Ai dreptate cu citirea, probabil nu e de acolo. Insa la mine toate testele iau TLE incepand cu testul 7, deci nici o altfel de grupare nu m-ar fi ajutat.

@Mihai Calancea:
Foarte tare ideea ...

Eu am luat 35 la Drumuri3 cu O(N ^ 3 * K + Q). Daca testele n-ar fi fost grupate as fi luat 60, dar banuiesc ca i-a afectat si pe altii, probabil implementarea n-a fost cea mai buna.

Problemele parca n-au fost totusi prea echilibrate, toata lumea a rezolvat Derdelus, iar foarte putini au facut ceva la Culoar. Ce nu mi-a placut a fost ca, fata de alte editii, n-am putut vedea evaluarea partiala decat la o singura problema. In rest site-ul s-a comportat foarte bine. :)

Dificultatea problemelor creste pe masura rundelor?

Trebuia programata saptamana urmatoare runda asta daca nu s-a putut programa dimineata de la 9.
Duminica de la ora 15 nu e o ora chiar potrivita... Nu stiu cata lume are chef de codat probleme algoritmice la ora asta duminica...
Eu de exemplu, m-am apucat de ele pe la ora 17:30-18. In rest pareau interesante problemele mai ales drumuri3 si culoar (is chiar curios cum se face aia).

Eu personal am muuuuult mai mult chef de la ora 15 decat de la 9 :)

Super tare runda. Super tare si problema Drumuri3. Keep up the good work. :D =D>

Felicitari pentru o runda foarte reusita.  :ok:

Nu neapărat, dar la Runda Finală cu siguranță vor fi probleme mai grele decât la rundele de calificare.


Nu puteam să programăm runda saptămâna viitoare, deoarece atunci va avea loc alt concurs.


Încă o data doresc să îmi cer scuze în numele echipei infoarena pentru problemele legate de funcționarea site-ului pe parcursul concursului. Deși s-a încercat rezolvarea acestor probleme, tot nu s-a ajuns la eliminarea totală a acestora.
Totuși, am o rugăminte pentru participanți: probabil aș fi putut afișa rezultatele cu 10 minute mai devreme dacă site-ul nu era supraîncarcat de request-uri datorită refresh-urilor pe clasament și monitorul de evaluare. Este foarte enervant și pentru noi sa tot încercăm să afișăm rezultatele, dar să nu reușim; există tentația să afișam rezultatele după 1 - 2 ore, când nu mai sunt atâtea refresh-uri, dar încercăm sa nu facem acest lucru. Așadar, la runda viitoare, încercați să nu mai faceți acest lucru și vă promit că în 2-3 minute se și afișeaza rezultatele.

Aceastea fiind spuse felicitări tuturor participanților, în special primilor clasați, și vă așteptăm la rundele viitoare!

Au fost interesante problemele. Acuma ca am vazut ideea pt drumuri3 mi se pare chiar f tare. Probabil ca runda asta a fost putin mai grea la open, pt ca 3 probleme au fost de la 10-12 fata de doua la runda I.
P.S.: Sa nu uitati sa updatati rating-urile  :D

A, si keep up the good work!

Daca postul tau a fost scris ca o gluma, a avut efect, deoarece am ras un pic :D. Sa vedem ce se intampla daca punem un concurs intr-o zi de vineri 13? :P
In cazul in care nu a fost o gluma, mi se pare ca exagerezi. Noi nu obligam pe nimeni sa faca nimic; daca convingerile tale nu te lasa sa scrii acel numar, atunci nu il scrii. Avem 1106 de probleme in arhiva, in afara de aceasta, deci ai de unde alege; ce nu iti place nu rezolvi.

Dupa ce m-am uitat la IP-ul tau mi-am dat seama cine esti, asa ca nu ma mai surpinde ce scrii pe forum. Nu este suficient ca ti-ai luat niste ban-uri pentru comportament inadecvat pe forum; acuma mai faci si trolling pe paginile concursului Algoritmiada.
Aici vin persoane interesate cu adevarat de informatica, care doresc sa invete ceva nou si sa se intalneasca cu persoane cu aceleasi pasiuni ca si ei. Asa ca nu mai posta doar ca sa pari interesant si sa umpli topicuri cu mesaje de-ale tale (care nu au nicio legatura cu subiectul topicului si care, apropo, pot fi sterse).

Hai ca asta e geniala.  :rotfl:

Postul despre numarul prim a fost util din punctul meu de vedere. Eu nu am observat ca e format din "el nombre del diablo" si din numarul ghinionist. Dar acuma ca s-a subliniat asta, am reusit sa retin un numar prim folositor la hashing(pana acuma trebuia sa-mi calculez unul). Concluzia: eu o sa folosesc numarul asta  :evil:

Pune modulo mult mai rar .... E cea mai costisitoare operație.

raspuns gresit la runda un la problema 2 pentru cazul in care 2k+1 este doar 3*2^t va rog daca puteti si aveti timp sa va aruncati un ochi peste ea