infoarena

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

Mie mi-au placut problemele, chiar daca am busit controlor (cum sa calculezi gresit memoria? In loc de vreo 5-6 mega cum calculasem aveam vreo 20 si ceva).
Bravo, tuturor!

Referitor la 5-9, nu pot sa spun decat

(http://i1.kym-cdn.com/photos/images/original/000/108/728/Oprah_umad.gif)

mda...problemele au fost cam simple...

Foarte tari problemele! Sunt curios cum se facea Bal... Eu am gasit o solutie, dar trebuia sa calculez det(matrice de adicenta) si asta imi cam busea timpu :-k. Banuiesc ca e cu vreo regula sau o optimizare in O(numarul de elemente nenule) a calcului determinantului.

Felicitari tuturor!!!  :thumbup:

Am facut o prostie. Am trimis din greaseala sursa la problema controlor la clasele 11-12 in loc de Open (eu participand la Open) si am pierdut astfel 100 de puncte la clasament. Se mai poate face ceva?

Se rezolva :)

Mie nu prea mi-a placut runda asta comparativ cu rundele trecute si cele din 2011. Gruparea testelor la bal a fost foarte nefericita(cel putin pentru mine), problemele, zic eu, n-au fost gradate dupa dificultate, toate 3 mi s-au parut grele, controlor greu de inteles. Pana acum problemele de la algoritmiada erau formulate clar si intelegeai rapid ce se cere. :(

Cu toate astea mi-a placut problema bal :) . Ce solutii ati gasit ?

Se poate face contestatie la Controlor? Ca la Open intra in timp si iau 100, in timp ce la 11-12 imi iese din timp si iau numai 90.  :angry:

Edit: Multumesc  :)

A fost o runda foarte buna  :wink:

Foarte misto runda asta, mi se pare cea mai tare de pina acum! Problemele chiar marfa, mai ales Bal si Swaps!

Keep up the good work!

Gruparea la bal nu a fost nefericita, ci din contra, a fost excelenta. Solutiile gresite nu merita puncte :P

Fixed!

Felicitari pentru subiecte si organizare  :peacefingers: Mi-au placut problemele la clasa a X-a si astept un articol cu solutii,caci sunt foarte curios cum se facea Swaps   :-k

Pe scurt, o dinamica cu exponentiere de matrice.

Felicitari organizatorilor pentru aceasta runda!

Alegerea problemelor mi s-a parut super, la cat mai multe runde cu acest format!

Astept cu nerabdare aparitia solutiilor oficiale!

Felictari echipei pentru o runda tare, organizata cu mai putini oameni decat de obicei =D>
Sa o tineti tot asa!

La swaps am obtinut o recurenta de genu f (p) = a * f (p-1) + b, care se rezolva asa:

f (p) = f (0) * a^n + b * ((a^n) - 1) / (a - 1)

si care se poate calcula cu exponentiere in timp logaritmic fara matrice  :D

Eu am luat 90 in concurs la clasele XI-XII si 100 in arhiva  :readthis: http://infoarena.ro/job_detail/692184 (http://infoarena.ro/job_detail/692184) . Nu se poate reevalua?

Fixed!

Asa mai merge  :D. Multumesc.
P.S: Felicitari organizatorilor.  =D>

Poate ar fi indicat sa anuntati rundele putin mai devreme decat cu cateva ore inainte de inceperea lor, pentru cei care nu stau toata ziua pe infoarena (chiar daca verificasem joia si inca nu era nimica pe site - cel putin pe pagina principala). Nu toata lumea isi verifica mailul din 2 in 2 ore si nu pentru toata lumea e trivial sa-si faca timp liber, chiar daca e vorba de duminica dimineata. In anii trecuti toate rundele au fost anuntate prin email cu zile bune inainte de inceperea lor, iar in acest an runda 2 nici n-a fost anuntata, iar runda 3 doar sambata seara (sau cel putin eu atunci am primit mailul).

La mine se poate modifica runda de la 11-12 la Open la problema controlor?

Runda a 3-a era anuntata pe prima pagina de vreo 2 - 3 saptamani :)

Unde are loc runda finala?

Fixed!

@SleepyOverlod: Vom trimite newsletterul la timp data viitoare! Ne cerem scuze! :(

@andrici_cezar: Cel mai probabil in Targu Mures.

Multumesc mult wefgef!

Ratingurile au fost updatate.

@SleepyOverlord: Ne pare rau pentru newsletterul trimis tarziu. Aparent am fost blacklisted pentru spam si mailurile pentru runda 2 si infoarena monthly n-au ajuns la toata lumea. Am realizat problema abia ieri si pare ca de data asta mailurile au ajuns.

Am actualizat solutia pentru problema Controlor. Scuzati eventualele greseli :) . Totodata ar fi mai bine daca articolului cu solutii i s-ar acorda o importanta mai mare, deoarece de exemplu si pentru Runda a 2-a doar unei probleme i s-a explicat solutia.

Sunteti invitati sa completati solutiile la toate problemele pe care le-ati rezolvat. De asta avem wiki! :banana:

Am adaugat solutia pentru problema Swaps. Rog pe cineva cu skill-uri in LaTeX sa modifice matricele( Eu tot luam LaTeX Error 3 si pana la urma am pus imagini :D ).

 Citat: "1. Numarul de interschimbari posibile este N² / 2".
Din enuntul problemei reiese altceva:
" deoarece avem 9 posibilitati de alegere a pozitiilor interschimbate, (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), dintre care doar doua produc rezultatul dorit ((1, 2) si (2, 1)). " (n=3)
Cum e corect? Daca ar fi sa ne luam dupa articolul de solutii, pentru n impar nici nu e un numar intreg de posibilitati. Formula cred eu ca ar fi n*(n+1)/2, pentru fiecare prim element alegand al doilea element mai mare sau egal decat el (suma n+(n-1)+(n-2)+...+1). Totusi, am preferat sa nu modific, pentru ca nu sunt lamurit.

Am modificat. Era greseala mea. Chestia este ca eu prin acel "/ 2" am incercat sa simplific calculele ulterioare. Numarul de interschimbari posibile este N ^ 2( pentru fiecare pozitie avem N pozitii cu care o putem schimba).

Bravo pentru solutii!
Mi se pare ca ai scris cam mult pentru acele solutii neoptimizate...
Pentru solutie de O(T*P) se considera pentru fiecare pas i (de la 1 la P) probabilitatea ca A sa fie pe pozitia B, sa ii zicem acesteia p; p se calculeaza folosind relatia p = p*P1 + (1-p) * P2 , de P ori. Unde P1 e probabilitatea de a nu schimba pozitia lui A ( ((n-1)*(n-1)+1)/N^2 ) iar P2 este probabilitatea de a schimba pozitia lui A pe pozitia B ( 2/N^2 ) . p fiind initial 1 daca A=B, 0 in caz contrar.

[...pornim de la urmatoarea idee: fiind intr-un pas i si stiind probabilitatea p ca la acel pas A sa fie pe pozitia B atunci pentru a ajunge in i+1 A pe pozitia B putem ori sa luam probabilitatea ca A sa se afle deja pe B si sa nu schimba pozitia acestuia, sau probabilitatea ca A sa nu se afle pe B si sa schimbam pozitia lui A pe B...]

Stiu ca si tu la solutia 3 ai scris cam acelasi lucru, dar mi se pare mai usor de explicat direct asa.Deci nu trebuie matrice, pentru ca ne intereseaza doar daca A este pe B sau nu, nu pozitia pe care este A. Daca vrei poti sa modifci articolul, mi se pare mai usor de inteles asa, si se implementeaza in doar 30 linii.

Eu de fapt prin acele multe solutii neoptimizate, am vrut sa arat in ce ordine ar trebui sa vina ideile; adica sa arat cum se trece de la solutia N^2 * P la solutia buna. Multumesc mult pentru feedback( voi modifica ceva mai pe seara :) ).

Unde asi putea sa vad si eu aceste soluti oficiale, sunt nou pe aici si nu prea stiu.

http://infoarena.ro/algoritmiada-2012/runda-3/solutii

Nu se gaseste nimeni care sa puna solutia pentru Bal?  :'(

Am scris eu solutia problemei Bal in articolul (http://infoarena.ro/algoritmiada-2012/runda-3/solutii) cu solutii.
P.S.: Daca am gresit ceva,  va rog corectati!