h1. Rotatie lexicografic minima
(Categoria _Algoritmi_, autor(i) _Mircea Pasoi_)
== include(page="template/implica-te/scrie-articole" user_id="m_dersidan") ==
Acest articol reprezinta un studiu de caz al unei probleme care poate fi considerata "clasica", fiind studiata inclusiv de cunoscutul profesor Edsger Wybe Dijkstra. Deoarece problema a apaput recent la diverse concursuri de informatica, prezinta interes pentru cei care se pregatesc pentru participarea la acestea.
(Categoria _Algoritmi_, Autor _Mircea Pasoi_)
Acest articol reprezinta un studiu de caz al unei probleme care poate fi considerata "clasica", fiind studiata inclusiv de cunoscutul profesor Edsger Wybe Dijkstra. Deoarece problema a aparut recent la diverse concursuri de informatica, prezinta interes pentru cei care se pregatesc pentru participarea la acestea.
h2. Enunt
In continuare vom prezenta doua formulari ale acestei probleme care au aparut recent la concursuri:
Cateodata programatorii au metode din cele mai diverse pentru a-ai ascunde parolele. De exemplu, sa vedem cum Billy "Hacker" Geits isi ascunde propriile parole. Billy isi alege un sir de caractere de lungime L < 100.000 format din litere mici ale alfabetului latin. Pentru acest sir de caractere Billy face toate cele L-1 deplasari circulare la stanga cu o pozitie si le pune unele sub altele. Dintre aceste L-1 siruri astfel obtinute, inaintea carora se trece sirul initial, se alege cel care este primul in ordine lexicografica, parola constituind-o un prefix al acestuia.
Scrieti un program care pentru un sir S dat determina pozitia celei "mai mici"(primei) deplasari in ordine lexicografica. Daca cel mai mic sir de caractere apare de mai multe ori, se se cere cea mai mica pozitie pe care acesta incepe.
_(ACM 2003-2004, regionala Europei de sud-est)_
Cateodata programatorii au metode din cele mai diverse pentru a-si ascunde parolele. De exemplu, sa vedem cum Billy "Hacker" Geits isi ascunde propriile parole. Billy isi alege un sir de caractere de lungime $L < 100.000$ format din litere mici ale alfabetului latin. Pentru acest sir de caractere Billy face toate cele $L-1$ deplasari circulare la stanga cu o pozitie si le pune unele sub altele. Dintre aceste $L-1$ siruri astfel obtinute, inaintea carora se trece sirul initial, se alege cel care este primul in ordine lexicografica, parola constituind-o un prefix al acestuia.
Scrieti un program care pentru un sir $S$ dat determina pozitia celei "mai mici" (primei) deplasari in ordine lexicografica. Daca cel mai mic sir de caractere apare de mai multe ori, se se cere cea mai mica pozitie pe care acesta incepe.
(ACM $2003-2004$, regionala Europei de sud-est)
Intr-un seif se afla niste documente pe care trebuie sa le extrageti. Problema este ca seiful este prevazut cu un terminal care necesita introducerea unei parole pentru a putea deschide seiful. La accesarea seifului, pe ecranul terminalului este afisat un cuvant cheie format din litere mici ale alfabetului englezesc. Parola este data de cea mai mica rotatie la stanga (in ordine lexicografica) a cuvantului cheie.
Fisierul de intrare _password.in_ contine pe prima linie un sir de caractere format din litere mici ale alfabetului englezesc. Lungimea sirului din fisierul de intrare este un numar intreg cuprins intre 1 si 100.000.
Fisierul de iesire _password.out_ trebuie sa contina un singur numar care reprezinta numarul de deplasari circulare la stanga ale sirului din fisierul de intrare necesare pentru a obtine parola de acces ceruta. Daca exista mai multe solutii va fi aleasa cea care necesita un numar minim de deplasari circulare la stanga.
_(Bursele Agora 2003-2004, Runda 44)_
Fisierul de intrare $_password.in_$ contine pe prima linie un sir de caractere format din litere mici ale alfabetului englezesc. Lungimea sirului din fisierul de intrare este un numar intreg cuprins intre $1$ si $100 000$.
Fisierul de iesire $_password.out_$ trebuie sa contina un singur numar care reprezinta numarul de deplasari circulare la stanga ale sirului din fisierul de intrare necesare pentru a obtine parola de acces ceruta. Daca exista mai multe solutii va fi aleasa cea care necesita un numar minim de deplasari circulare la stanga.
(Bursele Agora $2003-2004$, Runda $44$)
h2. Solutia naiva
O solutie triviala de complexitate O(N^2^) poate fi obtinuta parcurgand succesiv rotatiile si tinand cont de faptul ca compararea a doua siruri are complexitatea O(N) in cel mai defavorabil caz. Prezentam in continuare pseudocodul:
O solutie triviala de complexitate $O(N^2^)$ poate fi obtinuta parcurgand succesiv rotatiile si tinand cont de faptul ca compararea a doua siruri are complexitatea $O(N)$ in cel mai defavorabil caz. Prezentam in continuare pseudocodul:
== code(c) |
scrie min
==
h2. Solutia O(N*logN)
h2. Solutia $O(N*log N)$
Precizam intai ca atat o solutie O(N*lg^2^N) cat si una O(N*lgN) 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*lgN), 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 [log2 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.
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}.
|_=. i|_=. *...*|_=. *j-1*|=. *j*|=. *...* |=. *2j-i-1*|={background:gray}. *2j-i*|={background:gray}. *...*|={background:gray}. *$0$*|={background:gray}. *...*|={background:gray}. *i-1*|
|_=. $i$|_=. $*...*$|_=. $*j-1*$|=. $*j*$|=. $*...*$|=. $*2j-i-1*$|={background:gray}. $*2j-i*$|={background:gray}. $*...*$|={background:gray}. $*0*$|={background:gray}. $*...*$|={background:gray}. $*i-1*$|
*A = i...j-1*
*B = j...2j-i-1*
*C = 2j-i...i-1* (indicii sunt considerati mod N )
$*A = i...j-1*$
$*B = j...2j-i-1*$
$*C = 2j-i...i-1*$ (indicii sunt considerati $modulo N$ )
Fie sirul R ~i~ impartit in trei bucati A, B, C, ca in figura de mai sus. Conform figurii R ~i~ = ABC, iar R ~j~ = BCA, bucatile A si B avand fiecare j-i caractere. Comparand doar primele j-i caractere, vom compara bucatile A si B, astfel:
Fie sirul $R ~i~$ impartit in trei bucati $A$, $B$, $C$, ca in figura de mai sus. Conform figurii, $R ~i~ = ABC$, iar $R ~j~ = BCA$, bucatile $A$ si $B$ avand fiecare $j-i$ caractere. Comparand doar primele $j-i$ caractere, vom compara bucatile $A$ si $B$, astfel:
* 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 -> 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~ )$
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};
scrie L[1]
==
Spre exemplu, pentru sirul S = ("m", "i", "s", "s", "i", "s", "s", "i", "p", "p", "i") lista va contine initial elementele {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Spre exemplu, pentru sirul $S = ("m", "i", "s", "s", "i", "s", "s", "i", "p", "p", "i")$ lista va contine initial elementele ${0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}$
La primul pas se efectueaza (caracterele ingrosate sunt cele ce se vor compara):
R0 = mississippi > R1 = ississippim
R2 = ssissippimi = R3 = sissippimis
R4 = issippimiss < R5 = ssippimissi
R6 = sippimissis > R7 = ippimississ
R8 = ppimississi = R9 = pimississip
Lista va fi acum {1, 2, 4, 7, 8, 10}
$R0 = mississippi > R1 = ississippim$
$R2 = ssissippimi = R3 = sissippimis$
$R4 = issippimiss < R5 = ssippimissi$
$R6 = sippimissis > R7 = ippimississ$
$R8 = ppimississi = R9 = pimississip$
Lista va fi acum ${1, 2, 4, 7, 8, 10}$
Pasii urmatori sunt:
R1 = ississippim < R2 = ssissippimi
R4 = issippimiss > R7 = ippimississ
R8 = ppimississi > R10 = imississipp
L = {1, 7, 10}
R1 = ississippim > R7 = ippimississ
L = {7, 10}
R7 = ippimississ > R10 = imississipp
L = {10}
_TODO : add image_
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:
* *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~)
* *S[min+l] > S[p+l]* -> asemanator cu cazul anterior putem concluziona ca R ~min+i~ > R ~p+i~ pentru 0 <= i <=
l; asadar putem face doua observatii:
1) R ~min+i~ (0 <= i <= l) nu poate candida la solutie, si cum se stia dinainte ca nici R ~0~, R ~1~, ... R ~min-1~ nu pot, primul candidat posibil este R ~min+l+1~;
2) Cum R ~min~ era candidatul pana in prezent, iar R ~p~ < R ~min~, din R ~0~, R ~1~, ... R ~p~ singurul candidat posibil este R ~p~.
Variabila min va deveni max(min+l+1, p), p va deveni max(min+l+1, p)+1, iar l va fi egal cu 0.
$R1 = ississippim < R2 = ssissippimi$
$R4 = issippimiss > R7 = ippimississ$
$R8 = ppimississi > R10 = imississipp$
$L = {1, 7, 10}$
$R1 = ississippim > R7 = ippimississ$
$L = {7, 10}$
$R7 = ippimississ > R10 = imississipp$
$L = {10}$
p=. !rotatie-lexicografic-minima?image1.jpg!
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) mod N])$, iar in functie de rezultat se va lua o decizie:
* $*S[min+l] = S[(p+l) mod N]* ->$ se va incrementa variabila $l$ cu o unitate deoarece inca o pereche de caractere se potrivesc
* $*S[min+l] < S[(p+l) mod N]* ->$ 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~$)
* $*S[min+l] > S[(p+l) mod N]* ->$ asemanator cu cazul anterior putem concluziona ca $R ~min+i~ > R ~p+i~$ pentru $0 ≤ i ≤ l$; asadar putem face doua observatii:
$1) R ~min+i~ (0 <= i <= l)$ nu poate candida la solutie, si cum se stia dinainte ca nici $R ~0~, R ~1~, ... R ~min-1~$ nu pot, primul candidat posibil este $R ~min+l+1~$;
$2) Cum R ~min~$ era candidatul pana in prezent, iar $R ~p~ < R ~min~$, din $R ~0~, R ~1~, ... R ~p~$ singurul candidat posibil este $R ~p~$.
Variabila $min$ va deveni $max(min+l+1, p)$, $p$ va deveni $max(min+l+1, p)+1$, iar $l$ va fi egal cu $0$.
Un aspect al acestui algoritm care ar putea parea "misterios" este motivul pentru care complexitatea este liniara. Vom considera T = min+p+l si putem observa ca dupa fiecare comparatie T creste cu cel putin o unitate. Cum niciuna din cele trei variabile nu poate depasi valoarea N, numarul de iteratii este proportional cu N (se poate arata ca nu va depasi 2*N-3), de unde si complexitatea O(N).
Un aspect al acestui algoritm care ar putea parea "misterios" este motivul pentru care complexitatea este liniara. Vom considera $T = min+p+l$ si putem observa ca dupa fiecare comparatie $T$ creste cu cel putin o unitate. Cum niciuna din cele trei variabile nu poate depasi valoarea $N$, numarul de iteratii este proportional cu $N$ (se poate arata ca nu va depasi $2*N-3$), de unde si complexitatea $O(N)$.
==code(c) |
min <- 0; p <- 1; l <- 1;
cat timp (p < N) AND (min+l+1 < N) executa
daca S[min+l] = S[p+l] atunci l <- l+1;
daca S[min+l] < S[p+l] atunci p <- p+l+1; l <- 0;
daca S[min+l] > S[p+l] atunci min <- max(min+l+1, p); p <- min+1; l <- 0;
daca S[min+l] = S[(p+l) mod N] atunci l <- l+1;
daca S[min+l] < S[(p+l) mod N] atunci p <- p+l+1; l <- 0;
daca S[min+l] > S[(p+l) mod N] atunci min <- max(min+l+1, p); p <- min+1; l <- 0;
sfarsit cat timp
scrie min
==
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
Vom simula algoritmul pentru sirul $S = ("m", "i", "s", "s", "i", "s", "s", "i", "p", "p", "i").$
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, "problema 232":http://acm.sgu.ru/problem.php?contest=0&problem=232)*
$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...$
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)$
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...
Sa se gaseasca cel mai mare element ca valoare din sirul A, si sa se tipareasca primele N zecimale ale sale.
Se considera un sir $c ~1~ c ~2~ ...c ~n~$ format din $n ≤ 30.000$ caractere din multimea ${A, B}$. Concatenam sirul cu el insusi si obtinem un sir de lungime $2n$. Pentru un indice $k (1≤k≤2n)$ consideram subsecventele de lungime cel mult $n$, care se termina pe pozitia $k$, iar dintre acestea fie $s(k)$ subsecventa cea mai mica in ordine lexicografica. Determinati indicele $k$ pentru care $s(k)$ are lungimea cea mai mare.
*Problema 2 (Selectia lotului international, 2004)*
$Problema 3$
Se considera un sir c ~1~ c ~2~ ...c ~n~ format din n <= 30.000 caractere din multimea {A, B}. Concatenam sirul cu el insusi si obtinem un sir de lungime 2n. Pentru un indice k (1<=k<=2n) consideram subsecventele de lungime cel mult n, care se termina pe pozitia k, iar dintre acestea fie s(k) subsecventa cea mai mica in ordine lexicografica. Determinati indicele k pentru care s(k) are lungimea cea mai mare.
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 3*
$Problema 4$
Se dau doua poligoane in plan fiecare avand n<=1000000 varfuri. Poligoanele sunt date prin coordonatele varfurilor lor in ordine trigonometrica. Sa se verifice daca cele doua poligoane sunt asemenea.
Problema "password":problema/password de pe "infoarena":http://infoarena.ro.
h2. Bibliografie
[1] "Siruri de sufixe" (Cosmin Negruseri, Adrian Vladu), GInfo 15/7, noiembrie 2005
[2] "Solutii rundele 41-50" (Cosmin Negruseri), GInfo 14/5
[3] "http://www.cs.utexas.edu/users/EWD/":http://www.cs.utexas.edu/users/EWD/
# "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/
