Diferente pentru autumn-warmup-2007/solutii/runda-3 intre reviziile #12 si #53

Nu exista diferente intre titluri.

Diferente intre continut:

h2. 'Dk':problema/dk
Pentru problema existau diverse rezolvari brute-force, care in functie de calitatea implementarii af fi obtinut pana la $50$ de puncte.
Algoritmul folosit in rezolvarea pentru $100$ de puncte este Miller-Rabin. Este un algoritm probabilistic care verifica primalitatea unui numar in complexitate $O(c*log Nr)$, unde c este numarul de baze folosite pentru verificare.
Dorim sa verificam daca numarul $n$ este prim. Primul pas care trebuie efectuat este acela de a-l scrie pe $n-1$ ca numar de forma <tex>2^s^ * d</tex>, unde s trebuie sa fie maxim. Pasul urmator este sa verificam 2 relatii:
1. <tex> a^{d}\ mod\ n\ \neq\ 1 </tex>
2. <tex> a^{2^r*d}\ mod\ n\ \neq\ -1</tex>, pentru orice $0 &le; r &le; s-1$
 
Daca ambele relatii sunt simultan indeplinite pentru un numar $a$, atunci stim ca numarul $Nr$ este compus. Daca cel putin una dintre conditii nu este indeplinita se continua verificarile pentru un alt numar $a$. Numerele $a$ cu care se vor face verificarile pot fi, de exemplu, primele 6 numere prime sau o multime de numere prime alese aleator (mai mult de $3$, dar nu mai mult de $7$, pentru ca solutia sa se incadreze in timp).
Complexitatea logaritmica a algoritmului provine de la faptul ca ridicarile la putere se vor efectua in $O(log n)$. Pentru mai multe detalii consultati CLR-ul sau 'Wikipedia':http://en.wikipedia.org/wiki/Miller-Rabin_primality_test.
 
 
h2. 'Kcity':problema/kcity
h3. "Bandwidth"-ul si "Pathwidth"-ul unui graf
h2. 'Consir':problema/consir
Sa presupunem ca dorim sa aflam rezultatul pentru secventa maximala $1, 2 ... M$. Fie $F{~1~}, F{~2~}, ... F{~M~}$ frecventele numerelor de la $1$ la $M$ (numarul de aparitii). Sa construim acum un vector $P$ cu semnificatia $P{~i~} = F{~1~}* F{~2~} * ... * F{~M~}$. Datoria faptului ca rezultatul este mai mic decat $2^63^$ este clar ca nu avem mai mult de 63 de pozitii pentru care $F{~i~}>1$, deci la fiecare pas trebuie sa updatam subsecventele care se termina intr-o pozitie cu $F{~i~}>1$. Algoritmul in pseudocod pentru a calcula vectorul $Res$ cu semnificatia $Res{~i~}$ egal cu numarul de consiruri de lungime $i$ devine
Sa presupunem ca dorim sa aflam rezultatul pentru secventa maxima $1, 2 ... M$. Fie $F{~1~}, F{~2~}, ... F{~M~}$ frecventele numerelor de la $1$ la $M$ (numarul de aparitii). Sa construim acum un vector $P$ cu semnificatia $P{~i~} = F{~1~}* F{~2~} * ... * F{~i~}$. Datoria faptului ca rezultatul este mai mic decat $2^63^$ este clar ca nu avem mai mult de 63 de pozitii pentru care $F{~i~}>1$, deci la fiecare pas trebuie sa updatam subsecventele care se termina intr-o pozitie cu $F{~i~}>1$. Algoritmul in pseudocod pentru a calcula vectorul $Res$ cu semnificatia $Res{~i~}$ egal cu numarul de consiruri de lungime $i$ devine
== code(c) |
Res[M] = P[M];
pentru i = n-1, 1 executa
   Res[i] = Res[i+1] + P[M]/P[M-i];
   pentru j astfel incat F[j] >= 2 si j >= i+1
       Res[i] = Res[i] - P[j]/P[j-i-1] + P[j]/P[j-i];
       Res[i] = Res[i] - P[j]/P[j-i-1] + P[j-1]/P[j-i-1];
   sfarsit pentru
sfarsit pentru
==
h2. 'Polig':problema/polig
La problema polig sunt mai multe solutii, o idee ar fi ca numerele sa fie sortate dupa unghiul cu ox, aceasta era necesara sa se evite un caz particular in solutie. Iar dupa o dinamica $a[i][j]$ = care inseamna maximul astfel incat poligonul sa ajunga pana la segmentul i,j, recurenta iese o({$n$}), in total memorie este o(n^2^) si o(n^3^) complexitate. Mai este o solutie ceva mai faina, dar aceea solutie are copyright Mugurel Ionut Andreica si o las la latitudinea concurentilor, nu necesita cunostinte suplimentare asa ca ar fi interesant ca exercitiu.Hint ca sa nu incercati sa faceti o({$n$}): Complexitatea la solutia lui Mugurel avea sa fie o({$n^2^ lg{~2~}n$}).
 
Exista mai multe solutii care se incadreaza in timp pentru limitele date, o idee ar fi ca punctele sa fie sortate dupa unghiul cu axa $Ox$. Apoi, folosind programare dinamica vom construi o matrice cu semnificatia $a[i][j]$ = costul maxim astfel incat sa plecam din orginea planului si sa construim un drum care are ultimele puncte $i$ si $j$. In total, memoria este $O(n^2^)$ si complexitatea in timp $O(n^3^)$. Exista o solutie $O(n^2^ lg{~2~}n)$ propusa de Mugurel Ionut Andreica, gasirea ei o lasam ca un exercitiu pentru cititori :-). Daca aveti nelamuriri nu ezitati sa folositi forumul.

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.