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 existe pentru sirurile $A{~1..i~}$ si
$B{~1..~}$ (evident modulo {$666013$}). Se calculeaza $Nr{~i,j~}$ doar atunci cand {$A{~i~} = B{~i~}$}, 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
Primele 5 locuri din clasamentul de la 11-12 arata astfel:
1. Simion Filip - 200p
2. Macarie & Petronela - 190p
2. Fechete Dan Ionut - 190p
2. Crestez Leonard - 190p
3. Bindea Calin - 170p
4. Grosu Codrut - 140p
5. Gordon Freeman - 130p
5. Giurgea Mihnea - 130p
# Simion Filip - 200p
# Macarie & Petronela - 190p
# Fechete Dan Ionut - 190p
# Crestez Leonard - 190p
# Bindea Calin - 170p
# Grosu Codrut - 140p
# Gordon Freeman - 130p
# Giurgea Mihnea - 130p
h3. Iepuri
