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..~}$ (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
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
==Rankings(rounds="preoni51b" display_entries="6" pager_style="none")==
h3. Iepuri
Problema a fost cea mai usoara din cel 3 si necesita cunostiine elementare de matematica de clasa a 11-a. Daca se noteaza cu I(n) cati iepuri sunt in ziua n se deduc urmatoarele relatii din enunt:
I(0)=X, I(1)=Y, I(2)=Z
I(n)=A*I(n-1) + B*I(n-2) + C*I(n-3) pt n>=3
Rezultatul cerut este I(N) modulo 666013 pentru fiecare test.
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:
Problema a fost cea mai usoara din cel $3$ si necesita cunostiine elementare de matematica de clasa a 11-a. Daca se noteaza cu $I{~n~}$ cati iepuri sunt in ziua $n$ se deduc urmatoarele relatii din enunt:
* $I{~0~}=X, I{~1~}=Y, I{~2~}=Z$
* $I{~n~}=A*I{~n-1~} + B*I{~n-2~} + C*I{~n-3~}$ pt 3 ≤ n
[0 1 0]
Rezultatul cerut este $I{~N~}$ modulo $666013$ pentru fiecare test.
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]
M = [0 0 1]
[C B A]
[C B A]
care sta la baza relatiei:
[I(n) ] [I(n+1)]
M * [I(n+1)] = [I(n+2)]
[I(n+2)] [I(n+3)]
p(pre).
[I{~0~}] [I{~1~}]
M * [I{~1~}] = [I{~2~}]
[I{~2~}] [I{~3~}]
Din asta se deduce:
[I(0)] [I(N) ]
M^N * [I(1)] = [I(N+1)]
[I(2)] [I(N+2)]
p(pre).
[I{~0~}] [I{~N ~}]
M^N^ * [I{~1~}] = [I{~N+1~}]
[I{~2~}] [I{~N+2~}]
astfel problema se reduce la a calcula M^N in O(lg N). Algoritmul de ridicare la putere in timp logaritmic este clasic si nu-l mai mentionez aici.
astfel problema se reduce la a calcula $M^N^$ in {$O(lg N)$}. Algoritmul de ridicare la putere in timp logaritmic este clasic si nu-l mai mentionez aici.
h3. Barbar
Problema este de nivel mediu si necesita cunostiinte elementare de teoria grafurilor. Se considera matricea initiala un graf cu R*C noduri, mai putin zidurile. Se face o parcurgere BF pentru a determina pentru fiecare casuta din matrice distanta pana la cel mai apropiat dragon. Astfel, se incepe BF-ul cu toate nodurile care corespund dragonilor inserate in coada (deci nu va fi doar un nod in coada la inceput). Complexitatea acestui pas este O(R*C). Se observa daca exista un traseu valid care trece prin casute situate la distanta >=x fata de cel mai apropiat dragon, atunci exista in mod evident un traseu valid care trece prin casute situate la distanta >=x-1 fata de cel mai apropiat dragon. Aceasta observatie duce la folosirea cautarii binare a rezultatului (vezi articolul de pe site pentru alte aplicatii). Pentru a verifica daca exista un traseu valid care trece doar prin casute situate la o anumita distanta fata de cel mai apropiat dragon se foloseste tot o parcurgere BF, astfel rezolvarea fiind
O(R*C*lg(R*C)).
Problema este de nivel mediu si necesita cunostiinte elementare de teoria grafurilor. Se considera matricea initiala un graf cu $R*C$ noduri, mai putin zidurile. Se face o parcurgere BF pentru a determina pentru fiecare casuta din matrice distanta pana la cel mai apropiat dragon. Astfel, se incepe BF-ul cu toate nodurile care corespund dragonilor inserate in coada (deci nu va fi doar un nod in coada la inceput). Complexitatea acestui pas este {$O(R*C)$}. Se observa daca exista un traseu valid care trece prin casute situate la distanta $≥x$ fata de cel mai apropiat dragon, atunci exista in mod evident un traseu valid care trece prin casute situate la distanta $≥x-1$ fata de cel mai apropiat dragon. Aceasta observatie duce la folosirea cautarii binare a rezultatului (vezi articolul de pe site pentru alte aplicatii). Pentru a verifica daca exista un traseu valid care trece doar prin casute situate la o anumita distanta fata de cel mai apropiat dragon se foloseste tot o parcurgere BF, astfel rezolvarea fiind
{$O(R*C*lg(R*C))$}.
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][(n1, n2.. nk)] = costul unui lant hamiltonian
de cost maxim care incepe din nodul i si trece prin nodurile n1, n2 .. nk. Relatia de recurenta este: A[i][(n1,n2..nk)] = max cost(i, nj) + A[nj][(n1,n2,nj-1,nj+1..nk)] 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...)
