h1. Rotatie lexicografic minima

(Categoria _Algoritmi_, autor _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.

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)

$R7 = ippimississ > R10 = imississipp$
$L = {10}$

!rotatie-lexicografic-minima?image1.jpg!

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])$, 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) mod N])$, 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:

* $*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 &le; i &le; 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$.

==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
==

$Problema 2 (Selectia lotului national, 2004)$

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 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 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$

Problema "password":http://infoarena.ro/problema/password de pe "infoarena":http://infoarena.ro.

Problema "password":problema/password de pe "infoarena":http://infoarena.ro.

h2. Bibliografie

3696