h2. Solutia $O(N*log N)$

Precizam intai ca atat o solutie $O(N*lg^2^ N)$ cat si una $O(N*lg N)$ pot fi obtinute folosind structura de date "siruri de sufixe" $[1]$. Din pacate aceste solutii nu sunt foarte usor de implementat, iar constanta din notatia $O$ este destul de mare cat sa merite cautarea unei solutii alternative. Vom prezenta in continuare o solutie de complexitate $O(N*lg N)$, mult mai usor de implementat odata ce este inteleasa.

Precizam intai ca atat o solutie $O(N*lg^2^ N)$ cat si una $O(N*lg N)$ pot fi obtinute folosind structura de date "siruri de sufixe" $(1)$. Din pacate aceste solutii nu sunt foarte usor de implementat, iar constanta din notatia $O$ este destul de mare cat sa merite cautarea unei solutii alternative. Vom prezenta in continuare o solutie de complexitate $O(N*lg N)$, mult mai usor de implementat odata ce este inteleasa.

Primul pas pentru obtinerea acestei solutii este folosirea unei strategii de tip "turneu", si anume la fiecare iteratie se pastreaza o lista cu rotatiile care ar putea fi minime. Initial lista va avea toate cele $N$ rotatii, iar de fiecare data se iau rotatiile doua cate doua din lista si se elimina cea mai mare dintre cele doua din punct de vedere lexicografic. Procesul se reia pana cand se obtine o lista cu un singur element, reprezentand rotatia minima. Cum la fiecare pas numarul de elemente din lista se injumateste, este usor de vazut ca procesul nu se va repeta de mai mult de $[log ~2~N]$ ori. Desi la prima vedere acest algoritm are timpul de rulare $O(N^2^*lg N)$, vom arata in continuare ca sunt suficiente $O(N)$ comparatii de caractere per total la fiecare repetare:

Primul pas pentru obtinerea acestei solutii este folosirea unei strategii de tip "turneu", si anume la fiecare iteratie se pastreaza o lista cu rotatiile care ar putea fi minime. Initial lista va avea toate cele $N$ rotatii, iar de fiecare data se iau rotatiile doua cate doua din lista si se elimina cea mai mare dintre cele doua din punct de vedere lexicografic. Procesul se reia pana cand se obtine o lista cu un singur element, reprezentand rotatia minima. Cum la fiecare pas numarul de elemente din lista se injumateste, este usor de vazut ca procesul nu se va repeta de mai mult de $[log ~2~ N]$ ori. Desi la prima vedere acest algoritm are timpul de rulare $O(N^2^*lg N)$, vom arata in continuare ca sunt suficiente $O(N)$ comparatii de caractere per total la fiecare repetare:

Fie $R ~i~$ si $R ~j~$ doua rotatii (presupunem fara a restrange generalitatea ca $i < j$) aflate pe pozitii consecutive in lista, care urmeaza sa fie comparate, una din fiind aleasa pentru eliminare. Vom demonstra in continuare ca este suficienta compararea acestor rotatii folosindu-ne doar de primele $j - i$ caractere.
table{border:1px solid black}.

* $A < B -> R ~i~ < R ~j~ -> se elimina R ~j~$
* $A > B -> R ~i~ > R ~j~ -> se elimina R ~i~$

* $A = B -> se elimina R ~j~ (se presupune ca R ~i~ < R ~j~ )$

* $A = B -> se elimina R ~j~ ( se presupune ca R ~i~ < R ~j~ )$

Este evident ca in primele doua cazuri decizia de eliminare este corecta. Daca $A = B$ , iar decizia luata de eliminare a fost gresita, anume $R ~i~ > R ~j~$, cum $R ~i~ = ABC = AAC$ si $R ~j~ = BCA = ACA$, inseamna ca $A > C$ (daca $A$ ar fi fost egal cu $C$ atunci $R ~i~ = R ~j~$, si nu ar mai fi contat ce element se elimina), deci elementul pastrat va fi oricum eliminat de rotatia $R ~2j-i~ = CAA$ sau de o alta rotatie care s-a dovedit a fi mai mica decat $CAA$ la pasii anteriori. La a i-a parcurgere a listei, distanta intre doua rotatii aflate pe pozitii consecutive in lista este maxim $2^(i-1)^$, iar in lista sunt cel mult $[ n / 2^(i-1)^ ]$ elemente, astfel facandu-se $O(N)$ comparatii. In acest mod obtinem un algoritm corect de complexitate $O(N * log N)$.

Este evident ca in primele doua cazuri decizia de eliminare este corecta. Daca $A = B$ , iar decizia luata de eliminare a fost gresita, anume $R ~i~ > R ~j~$, cum $R ~i~ = ABC = AAC$ si $R ~j~ = BCA = ACA$, inseamna ca $A > C$ (daca $A$ ar fi fost egal cu $C$ atunci $R ~i~ = R ~j~$, si nu ar mai fi contat ce element se elimina), deci elementul pastrat va fi oricum eliminat de rotatia $R ~2j-i~ = CAA$ sau de o alta rotatie care s-a dovedit a fi mai mica decat $CAA$ la pasii anteriori. La a i-a parcurgere a listei, distanta intre doua rotatii aflate pe pozitii consecutive in lista este maxim $2^i-1^$, iar in lista sunt cel mult $[ n / 2^i-1^ ]$ elemente, astfel facandu-se $O(N)$ comparatii. In acest mod obtinem un algoritm corect de complexitate $O(N * log N)$.

==code(c) |
L <- {0,1,2,...,N-1};

h2. Solutia $O(N)$

Vom incerca acum sa obtinem un algoritm de complexitate liniara folosind alte idei de rezolvare. Algoritmul pe care il vom propune in continuare functioneaza ca si algoritmul trivial mentionat mai sus, anume parcurgand rotatiile succesiv. La fiecare pas se vor pastra trei variabile $min, p, l$ cu semnificatia ca rotatiile $R ~0~, R ~1~, ... R ~p-1~$ au fost parcurse pana acum, iar $R ~min~$ este o rotatie dintre acestea care ar putea fi cea lexicografic minima (toate celelalte din cele parcurse sigur nu pot fi solutia finala). De asemenea, variabila $l$ va semnifica ca primele $l$ caractere din $R ~min~$ sunt egale cu primele $l$ caractere din $R ~p~$, $R ~p~$ fiind urmatoarea rotatie ce va fi procesata. Cunoscand aceste informatii, la fiecare pas se va compara al $l+1-lea$ caracter din $R ~min~$ ($S[min+l])$ cu al $l+1-lea$ din $R ~p~ (S[p+l]$), iar in functie de rezultat se va lua o decizie:

Vom incerca acum sa obtinem un algoritm de complexitate liniara folosind alte idei de rezolvare. Algoritmul pe care il vom propune in continuare functioneaza ca si algoritmul trivial mentionat mai sus, anume parcurgand rotatiile succesiv. La fiecare pas se vor pastra trei variabile $min, p, l$ cu semnificatia ca rotatiile $R ~0~, R ~1~, ... R ~p-1~$ au fost parcurse pana acum, iar $R ~min~$ este o rotatie dintre acestea care ar putea fi cea lexicografic minima (toate celelalte din cele parcurse sigur nu pot fi solutia finala). De asemenea, variabila $l$ va semnifica ca primele $l$ caractere din $R ~min~$ sunt egale cu primele $l$ caractere din $R ~p~$, $R ~p~$ fiind urmatoarea rotatie ce va fi procesata. Cunoscand aceste informatii, la fiecare pas se va compara al $l+1-lea$ caracter din $R ~min~$ $(S[min+l])$ cu al $l+1-lea$ din $R ~p~ (S[p+l])$, iar in functie de rezultat se va lua o decizie:

* $*S[min+l] = S[p+l]* ->$ se va incrementa variabila $l$ cu o unitate deoarece inca o pereche de caractere se potrivesc
* $*S[min+l] < S[p+l]* ->$ putem trage imediat concluzia ca $R ~min~ < R ~p~$ , iar mai mult, din faptul ca primele $l$ caractere se potrivesc putem spune ca $R ~min+i~ < R ~p+i~$ pentru $0 <= i <= l$; cum $R ~min~$ era rotatia "candidata" la solutia finala dintre $R ~0~, R ~1~, ... R ~p-1~$ si este mai mica ca $R ~p~$, iar pentru orice $R ~p+i~ (1 <= i <= l)$ exista $R ~min+i~ < R ~p+i~$, despre care se stie ca nu poate fi solutia finala, $R ~min~$ va repezenta in continuare rotatia candidata la solutie dintre $R ~0~, R ~1~, ... R ~p-1~, R ~p~, R ~p+1~, ... R ~p+l~$. Asadar $p$ va deveni $p+l+1$, iar $l$ va deveni $0$ (deoarece nu se cunosc inca informatii despre $R ~min~$ si $R ~p+l+1~$)

==
Vom simula algoritmul pentru sirul $S = ("m", "i", "s", "s", "i", "s", "s", "i", "p", "p", "i").$

$min = 0 p = 1 l = 0 ; S[min+l] = "m" > S[p+l] = "i" ->$
$min = 1 p = 2 l = 0 ; S[min+l] = "i" < S[p+l] = "s" ->$
$min = 1 p = 3 l = 0 ; S[min+l] = "i" < S[p+l] = "s" ->$
$min = 1 p = 4 l = 0 ; S[min+l] = "i" = S[p+l] = "i" ->$
$min = 1 p = 4 l = 1 ; S[min+l] = "s" = S[p+l] = "s" ->$
$min = 1 p = 4 l = 2 ; S[min+l] = "s" = S[p+l] = "s" ->$
$min = 1 p = 4 l = 3 ; S[min+l] = "i" = S[p+l] = "i" ->$
$min = 1 p = 4 l = 4 ; S[min+l] = "s" > S[p+l] = "p" ->$
$min = 6 p = 7 l = 0 ; S[min+l] = "s" > S[p+l] = "i" ->$
$min = 7 p = 8 l = 0 ; S[min+l] = "i" < S[p+l] = "p" ->$
$min = 7 p = 9 l = 0 ; S[min+l] = "i" < S[p+l] = "p" ->$
$min = 7 p = 10 l = 0 ; S[min+l] = "i" = S[p+l] = "i" ->$
$min = 7 p = 10 l = 1 ; S[min+l] = "p" > S[p+l] = "m" ->$
$min = 10$

 
table{example}.
|_=. $pas$|_=. $min$|_=. $p$|_=. $l$|_=. $S[min+l]$|_=. $S[p+l]$|_=. $caz$|
| $1$ | $0$ | $1$ | $0$ | $m$ | $i$ | $S[min+l] > S[p+l]$ |
| $2$ | $1$ | $2$ | $0$ | $i$ | $s$ | $S[min+l] < S[p+l]$ |
| $3$ | $1$ | $3$ | $0$ | $i$ | $s$ | $S[min+l] < S[p+l]$ |
| $4$ | $1$ | $4$ | $0$ | $i$ | $i$ | $S[min+l] = S[p+l]$ |
| $5$ | $1$ | $4$ | $1$ | $s$ | $s$ | $S[min+l] = S[p+l]$ |
| $6$ | $1$ | $4$ | $2$ | $s$ | $s$ | $S[min+l] = S[p+l]$ |
| $7$ | $1$ | $4$ | $3$ | $i$ | $i$ | $S[min+l] = S[p+l]$ |
| $8$ | $1$ | $4$ | $4$ | $s$ | $p$ | $S[min+l] > S[p+l]$ |
| $9$ | $6$ | $7$ | $0$ | $s$ | $i$ | $S[min+l] > S[p+l]$ |
| $10$ | $7$ | $8$ | $0$ | $i$ | $p$ | $S[min+l] < S[p+l]$ |
| $11$ | $7$ | $9$ | $0$ | $i$ | $p$ | $S[min+l] < S[p+l]$ |
| $12$ | $7$ | $10$ | $0$ | $i$ | $i$ | $S[min+l] = S[p+l]$ |
| $13$ | $7$ | $10$ | $1$ | $p$ | $m$ | $S[min+l] > S[p+l]$ |
| $14$ | $10$ | 0 | 0 | 0 | 0 | 0 |
 
si, in final, $min = 10$

h2. Aplicatii
$Problema 1 ("acm.sgu.ru":http://acm.sgu.ru, "Infinite fraction":http://acm.sgu.ru/problem.php?contest=0&problem=232)$
Se dau doua numere naturale $N<=150000$ si $K<=10^9^$ si un vector de cifre $D[0...N-1]$. Se va considera un sir $A$ de numere reale cu partea intreaga $0$, iar partea fractionara a elementului $A[i]$ va fi sirul infinit format din $D[(i+0*K) mod N], D[(i+1*K) mod N], D[(i+2*K) mod N]$ etc. Spre exemplu, pentru $N = 3, K = 2 si D = '194'$ se obtine:

$A[1] = 0.1491491491...$
$A[2] = 0.9149149149...$
$A[3] = 0.4914914914...$

$A[ 1 ] = 0.1491491491...$
$A[ 2 ] = 0.9149149149...$
$A[ 3 ] = 0.4914914914...$

Sa se gaseasca cel mai mare element ca valoare din sirul $A$, si sa se tipareasca primele $N$ zecimale ale sale.
$Problema 2 (Selectia lotului national, 2004)$

$Problema 3$

Se dau doua poligoane in plan fiecare avand $n<=1 000 000$ varfuri. Poligoanele sunt date prin coordonatele varfurilor lor in ordine trigonometrica. Sa se verifice daca cele doua poligoane sunt asemenea.

Se dau doua poligoane in plan fiecare avand $n <= 1 000 000$ varfuri. Poligoanele sunt date prin coordonatele varfurilor lor in ordine trigonometrica. Sa se verifice daca cele doua poligoane sunt asemenea.

$Problema 4$

h2. Bibliografie

# "Siruri de sufixe" (Cosmin Negruseri, Adrian Vladu), GInfo $15/7$, noiembrie $2005$
# "Solutii rundele $41-50$" (Cosmin Negruseri), GInfo $14/5$

# "Siruri de sufixe" (Cosmin Negruseri, Adrian Vladu), GInfo 15/7, noiembrie 2005
# "Solutii rundele 41-50" (Cosmin Negruseri), GInfo 14/5

# "E.W.Dijkstra Archive: Home page":http://www.cs.utexas.edu/users/EWD/