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. 'Polig':problema/polig

La problema polig sunt 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$}) data de Mugurel Ionut Andreica, gasirea ei o lasam ca un exercitiu pentru cititori :-). Daca aveti nevoie de ajutor nu ezitati sa folositi forumul.

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.