h3. Trapez

Problema a fost cea de nivel mediu din cele $3$ si face apel la cunostiinte minime de geometrie. Conditia ca oricare trei puncte nu sunt coliniare simplifica mult rezolvarea. Din definitie, un trapez are cel putin doua laturi paralele deci se poate construi urmatorul algoritm: se iau toate perechile de puncte - acestea determina cate un segment - si sorteaza in functie de unghiul cu axa OX (panta dreptei). Pentru fiecare $k$ segmente cu acelasi unghi se pot forma {$Comb(k,2)$} trapeze. Pentru a evita calculele cu reale (care pot cauza erori de precizie), se tin pantele ca perechi de numere intregi ({$y, x$}), fara a efectua efectiv impartirea {$y/x$}. Pentru compararea a doua astfel de perechi sunt necesare tipuri de date pe $64$ de biti. Algoritmul descris are complexitate {$O(N^2^*lg N)$}. Las ca exercitiu rezolvarea acestei probleme folosind un algoritm $O(N^2^)$ care foloseste "hashing":http://www.infoarena.ro/Hashing (vezi articolul de pe site). Se puteau obtine $40-50p$ cu un algoritm brut {$O(N^4^)$}.

Problema a fost cea de nivel mediu din cele $3$ si face apel la cunostiinte minime de geometrie. Conditia ca oricare trei puncte nu sunt coliniare simplifica mult rezolvarea. Din definitie, un trapez are cel putin doua laturi paralele deci se poate construi urmatorul algoritm: se iau toate perechile de puncte - acestea determina cate un segment - si sorteaza in functie de unghiul cu axa OX (panta dreptei). Pentru fiecare $k$ segmente cu acelasi unghi se pot forma {$Comb(k,2)$} trapeze. Pentru a evita calculele cu reale (care pot cauza erori de precizie), se tin pantele ca perechi de numere intregi ({$y, x$}), fara a efectua efectiv impartirea {$y/x$}. Pentru compararea a doua astfel de perechi sunt necesare tipuri de date pe $64$ de biti. Algoritmul descris are complexitate {$O(N^2^*lg N)$}. Las ca exercitiu rezolvarea acestei probleme folosind un algoritm $O(N^2^)$ care foloseste "hashing":tabele-hash-scurta-prezentare (vezi articolul de pe site). Se puteau obtine $40-50p$ cu un algoritm brut {$O(N^4^)$}.

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
$B{~1..i~}$ (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).

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{~N  ~}]
M * [I{~1~}] = [I{~N+1~}]
    [I{~2~}]   [I{~N+2~}]

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

Din asta se deduce:

h3. ADN

La primul pas se elimina toate cuvintele incluse in alte cuvinte mai mari (pentru a cauta daca exista un cuvant in alt cuvant se foloseste algoritmul KMP pentru incadrarea in timp - vezi articolul de pe site). Apoi, se construieste un graf cu noduri cuvintele si muchii intre oricare doua cuvinte. Costul unei muchii ({$i, j$}) va fi cel mai lung sufix al cuvantului $i$ care este prefix al cuvantului $j$ (informatie care se poate determina cu KMP), adica cate litere sunt "inutile" daca lipim cuvantul $i$ cu cuvantul {$j$}. Aceasta prima etapa are complexitate {$O(N^2^*L)$}, unde $L$ e lungimea maxima a unui cuvant. Deoarece trebuie sa existe fiecar cuvant in sirul rezultat, iar sirul sa fie de lungime minima problema se reduce la determinarea unui lant hamiltonian de cost maxim, problema care este binecunoscuta ca fiind {$NP$}. Un algoritm care incearca toate cele $n!$ permutari are complexitate $O(n!)$ si va obtine {$50p$}. Pentru punctaj maxim vom folosi programare dinamica astfel: fie {$A[i][(n{~1~}, n{~2~}.. n{~k~})]$} = costul unui lant hamiltonian de cost maxim care incepe din nodul $i$ si trece prin nodurile {$n{~1~}, n{~2~} .. n{~k~}$}. Relatia de recurenta este: {$A[i][n{~1~},n{~2~}..n{~k~})]$ = {$max cost(i, n{~j~}) + A[n{~j~}][(n{~1~},n{~2~},n{~j-1~},n{~j+1~}..n{~k~})]$} pentru fiecare {$j$}. Dinamica se initializeaza cu $A[i][(i)] = 0$ pentru fiecare {$i$}. Reprezentarea multimilor de noduri se face folosind un numar binar cu $N$ biti, astfel complexitatea acestei etape fiind {$O(N^2^*2^N^)$}. Mentionez ca aceasta rezolvare nu produce solutia minim lexicografic, fapt observat in timpul concursului si astfel s-a reevaluat problema dandu-se puncte pentru orice solutie valida, nu neaparat minim lexicografic. Rezolvarea problemei cu cerinta de minim lexicografic este posibila, dar pentru realizarea ei trebuie folosite structuri de date avansate ca Suffix Arrays sau Suffix Trees si nivelul de dificultate ar fi mult mai mare. Alta observarie este ca matricea cost ar putea fi calculata mai repede daca am folosi structurile mentionate mai devreme. Folosind prima structura am avea complexitatea $O( N*L log (N*L))$ iar a folosind a doua structura am avea complexitatea $O(N*L)$ . De asemenea mentionam posibilitatea folositii algoritmului randomizat de potrivire a sirurilor de caractere numit Rabin Karp pentru calcularea matricii cost ceea ce ar fi dus la o solutie mai scurta si la un cod mai clar. Ne cerem scuze pentru eventualele neplaceri cauzate de aceasta situatie.

La primul pas se elimina toate cuvintele incluse in alte cuvinte mai mari (pentru a cauta daca exista un cuvant in alt cuvant se foloseste algoritmul KMP pentru incadrarea in timp - vezi articolul de pe site). Apoi, se construieste un graf cu noduri cuvintele si muchii intre oricare doua cuvinte. Costul unei muchii ({$i, j$}) va fi cel mai lung sufix al cuvantului $i$ care este prefix al cuvantului $j$ (informatie care se poate determina cu KMP), adica cate litere sunt "inutile" daca lipim cuvantul $i$ cu cuvantul {$j$}. Aceasta prima etapa are complexitate {$O(N^2^*L)$}, unde $L$ e lungimea maxima a unui cuvant. Deoarece trebuie sa existe fiecar cuvant in sirul rezultat, iar sirul sa fie de lungime minima problema se reduce la determinarea unui lant hamiltonian de cost maxim, problema care este binecunoscuta ca fiind {$NP$}. Un algoritm care incearca toate cele $n!$ permutari are complexitate $O(n!)$ si va obtine {$50p$}. Pentru punctaj maxim vom folosi programare dinamica astfel: fie {$A[i][(n{~1~}, n{~2~}.. n{~k~})]$} = costul unui lant hamiltonian de cost maxim care incepe din nodul $i$ si trece prin nodurile {$n{~1~}, n{~2~} .. n{~k~}$}. Relatia de recurenta este: {$A[i][n{~1~},n{~2~}..n{~k~})]$ = {$max cost(i, n{~j~}) + A[n{~j~}][(n{~1~},n{~2~},n{~j-1~},n{~j+1~}..n{~k~})]$} pentru fiecare {$j$}. Dinamica se initializeaza cu $A[i][(i)] = 0$ pentru fiecare {$i$}. Reprezentarea multimilor de noduri se face folosind un numar binar cu $N$ biti, astfel complexitatea acestei etape fiind {$O(N^2^*2^N^)$}. Mentionez ca aceasta rezolvare nu produce solutia minim lexicografic, fapt observat in timpul concursului si astfel s-a reevaluat problema dandu-se puncte pentru orice solutie valida, nu neaparat minim lexicografic. Rezolvarea problemei cu cerinta de minim lexicografic este posibila, dar pentru realizarea ei trebuie folosite structuri de date avansate ca Suffix Arrays sau Suffix Trees si nivelul de dificultate ar fi mult mai mare. Alta observarie este ca matricea cost ar putea fi calculata mai repede daca am folosi structurile mentionate mai devreme. Folosind prima structura am avea complexitatea $O( N*L log (N*L))$ iar a folosind a doua structura am avea complexitatea $O(N*L)$ . De asemenea mentionam posibilitatea folosirii algoritmului randomizat de potrivire a sirurilor de caractere numit Rabin Karp pentru calcularea matricii cost ceea ce ar fi dus la o solutie mai scurta si la un cod mai clar. Ne cerem scuze pentru eventualele neplaceri cauzate de aceasta situatie.

Bafta la urmatorul concurs! (undeva prin februarie...)