h3. Subsir

Aceasta problema, care a fost si cea mai grea, a fost prezenta si la CEOI 2003, dar intr-o forma mai simpla. Acolo se cerea generarea efectiva a tuturor subsirurilor , nu numararea lor, si se garanta ca numarul lor este sub {$1000$}. Orice solutie care ar fi luat $100p$ la problema de la CEOI ar fi obtinut $50p$ la aceasta (primele $5$ teste fiind de fapt preluate de la CEOI 2003). Cum multi probabil au intuit, rezolvarea se bazeaza pe programare dinamica. Voi numi cele doua siruri $A$ si {$B$}, de lungime {$N$}, respectiv $M$ si voi construi initial matricea $C{~i,j~}$ = lungimea celui mai lung subsir comun al sirurilor {$A{~1..i~}$} si {$B{~1..j~}$}. Acest lucru se poate face in $O(N*M)$ si este o aplicatie clasica a programarii dinamice (se gaseste in foarte multe carti explicata ideea). In continuare voi numara sirurile folosind un algoritm $O(N*M*Sigma)$ unde $Sigma$ este numarul litere din care pot fi formate sirurile, adica {$26$}. Se va calcula o matrice $Nr{~i,j~}$ = cate subsiruri comune de lungime maxima existe pentru sirurile $A{~1..i~}$ si

Aceasta problema, care a fost si cea mai grea, a fost prezenta si la CEOI 2003, dar intr-o forma mai simpla. Acolo se cerea generarea efectiva a tuturor subsirurilor , nu numararea lor, si se garanta ca numarul lor este sub {$1000$}. Orice solutie care ar fi luat $100p$ la problema de la CEOI ar fi obtinut $50p$ la aceasta (primele $5$ teste fiind de fapt preluate de la CEOI 2003). Cum multi probabil au intuit, rezolvarea se bazeaza pe programare dinamica. Voi numi cele doua siruri $A$ si {$B$}, de lungime {$N$}, respectiv $M$ si voi construi initial matricea $C{~i,j~}$ = lungimea celui mai lung subsir comun al sirurilor {$A{~1..i~}$} si {$B{~1..j~}$}. Acest lucru se poate face in $O(N*M)$ si este o aplicatie clasica a programarii dinamice (se gaseste in foarte multe carti explicata ideea). In continuare voi numara sirurile folosind un algoritm $O(N*M*Sigma)$ unde $Sigma$ este numarul litere din care pot fi formate sirurile, adica {$26$}. Se va calcula o matrice $Nr{~i,j~}$ = cate subsiruri comune de lungime maxima exista pentru sirurile $A{~1..i~}$ si

$B{~1..j~}$ (evident modulo {$666013$}). Se calculeaza $Nr{~i,j~}$ doar atunci cand {$A{~i~} = B{~j~}$}, astfel: pentru fiecare caracter $c$ intre '{$a$}' si '{$z$}' se cauta ultima sa aparitie in sirul $A{~1..i-1~}$ (fie aceasta pozitia {$ii$}) si ultima sa aparitie in sirul $B{~1..j-1~}$ (fie aceasta pozitia {$jj$}). Acest lucru se poate face in $O(1)$ daca se preproceseaza inainte aceste informatii in {$O((N+M)*Sigma)$}. Daca $C{~i,j~} = C{~ii,jj~}+1$ se va aduna $Nr{~ii,jj~}$ la $Nr{~i,j~}$ - aceasta conditie ne garanteaza ca subsirurile adaugate au lungime maxima, iar faptul ca $ii$ si $jj$ reprezinta ultima aparitie a caracterului garanteaza ca nu se vor numara subsiruri identice. Pentru a gasi rezultatul final se aduna toate valorile $Nr{~i,j~}$ calculate, cu urmatoarea exceptie: daca exista pozitiile $x$ si $y$ astfel incat {$A{~x~} = A{~i~} = B{~y~} = B{~j~}$}, se aduna $Nr{~i,j~}$ doar daca $x < i$ si $y < j$ (pentru a asigura ca nu se numara subsiruri identice de mai multe ori).
h2. Clasele 11-12

O prima rezolvare, si cea mai simpla, este implementarea directa a relatiei de recurenta si conduce la o complexitate $O(N)$ pe set de date. Aceasta abordare ar fi obtinut {$50p$}.In continuare voi descrie o rezolvare $O(lg N)$ care foloseste matrici. Se construieste matricea:
p(pre).

    [0 1 0]

    [0 1 0]

M = [0 0 1]

    [C B A]

    [C B A]

care sta la baza relatiei:
p(pre).

    [I{~0~}]   [I{~1~}]

    [I{~0~}]   [I{~1~}]

M * [I{~1~}] = [I{~2~}]

    [I{~2~}]   [I{~3~}]

    [I{~2~}]   [I{~3~}]

Din asta se deduce: