Feedback Runda 3

[•bogdan2412]

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.

[•tzipleatud]

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.

[•wefgef]

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!

[•dushmi]

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 ).

[•andrei.finaru]

 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.

[•dushmi]

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).

[•Cristy94]

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 ).

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.

[•dushmi]

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 ).

[•maryan]

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

[•wefgef]

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

[•Rengel]

Nu se gaseste nimeni care sa puna solutia pentru Bal? 

[•MciprianM]

Am scris eu solutia problemei Bal in articolul cu solutii.
P.S.: Daca am gresit ceva,  va rog corectati!