Setul de probleme, impreuna cu testele si clasamentul, se gaseste in cadrul "sectiunii download":downloads. In continuare vom prezenta solutiile:

h2. Cover

h2(#cover). Cover

Problema nu era foarte dificila, cu atat mai mult cu cat ideea de rezolvare a problemei guards din concursul CEOI 2002 era aceeasi: se construieste un graf bipartit avand intr-o multime barele orizontale (set maximal de pozitii de pe o linie din matrice in care avem noroi) si in cealalta multime barele verticale (definite analog dar pentru coloane). Intre doua noduri din acest graf bipartit vom avea muchie doar daca barele corespunzatoare lor au o celula comuna. Pentru exemplificare vom lucra cu exemplul din enunt:
@*.*.@

Muchiile din graful bipartit vor fi urmatoarele:
$(1, 1) (2, 2) (3, 3) (3, 2) (3, 4) (4, 5) (4, 3) (4, 2) (5, 2)$

Asadar fiecarei celule din harta terenului ii corespunde o singura muchie in acest graf bipartit. Avand construit graful trebuie sa aflam numarul minim de noduri selectate astfel incat orice muchie sa aiba cel putin un capat intre nodurile selectate (in literatura de specialitate aceasta problema se numeste $Minimum Vertex Cover$). Explicatia acestui lucru este simpla: orice muchie, fiind de fapt o celula, ea trebuie sa fie "acoperita" de cel putin un nod din graf (adica o placa orizontala sau verticala utilizata de FJ). Problema acesta este NP-completa pentru grafuri generale dar in cazul grafurilor bipartite ea se poate rezolva in timp polinomial. De asemenea s-a demonstrat ca numarul minim de noduri dintr-un astfel de set este egal cu cardinalul cuplajului maximal din graful bipartit. De aici nu mai e decat un pas spre solutia finala. Avem, astfel, urmatorii pasi in algoritmul de rezolvare a problemei:

Asadar fiecarei celule din harta terenului ii corespunde o singura muchie in acest graf bipartit. Avand construit graful trebuie sa aflam numarul minim de noduri selectate astfel incat orice muchie sa aiba cel putin un capat intre nodurile selectate (in literatura de specialitate aceasta problema se numeste {$Minimum Vertex Cover$}). Explicatia acestui lucru este simpla: orice muchie, fiind de fapt o celula, ea trebuie sa fie "acoperita" de cel putin un nod din graf (adica o placa orizontala sau verticala utilizata de FJ). Problema acesta este NP-completa pentru grafuri generale dar in cazul grafurilor bipartite ea se poate rezolva in timp polinomial. De asemenea s-a demonstrat ca numarul minim de noduri dintr-un astfel de set este egal cu cardinalul cuplajului maximal din graful bipartit. De aici nu mai e decat un pas spre solutia finala. Avem, astfel, urmatorii pasi in algoritmul de rezolvare a problemei:

==code(cpp) |
* PAS 1: Construirea grafului bipartit
* PAS 2: Aflarea cuplajului maximal
==
Primul pas este banal si consta din simple parcurgeri ale matricii. Pentru aflarea cuplajului maximal se poate afla utilizand un algoritm de aflarea a fluxului maxim in reteaua asociata grafului bipartit sau se poate algoritmul bazat pe gasirea succesiva a drumurilor in crestere in graf.

Complexitatea finala a algoritmului va fi $O(N^2^*M^2^)$ deoarece in graful bipartit avem maxim $N*M$ muchii si vom $N*M$ noduri. Cum algoritmul pentru aflarea cuplajului maximal are complexitatea $V*E$ ($V$ = numarul de noduri din graf, $E$ = numarul de muchii din graf) concluzia este evidenta.

Complexitatea finala a algoritmului va fi $O(N^2^*M^2^)$ deoarece in graful bipartit avem maxim $N*M$ muchii si vom $N*M$ noduri. Cum algoritmul pentru aflarea cuplajului maximal are complexitatea $V*E$ ({$V$} = numarul de noduri din graf, $E$ = numarul de muchii din graf) concluzia este evidenta.

Ca tema, recomand rezolvarea urmatoarelor probleme a caror solutie se bazeaza pe aflarea cuplajului maximal intr-un graf bipartit (in unele cazuri acest lucru insa nu este de ajuns):
# $guards (CEOI 2002)$

  care au inaltimea mai mare decat inaltimea componentei
==

Se poate modifica usor algoritmul $FILL$ pentru a rezolva toate aceste cerinte. Complexitatea finala a algoritmului va fi $O(N^2^*logN)$ deoarece, in cazul cel mai defavorabil, toate celulele sunt turn (un exemplu este cand matricea este piramidala) si in consecinta toate celulele vor fi introduse si scoase din heap necesitand logN pentru fiecare operatie. Aflarea componentelor conexe va necesita $O(N^2^)$ timp in total fiindca o celula va fi selectata o singura data intr-o componenta conexa si va fi accesata de maxim 4 ori de algoritmul $FILL$. Ca detalii de implementare, programatorii in $C++$ pot folosi cozile de prioritati din $STL$ ($priority_queue$ ce se gaseste in headerul $<queue>$) pentru a reduce din complexitatea implementarii. Totusi, trebuie acordata atentie utilizarii acestora deoarece este posibil ca sursa sa depasesca timpul de executie.

Se poate modifica usor algoritmul $FILL$ pentru a rezolva toate aceste cerinte. Complexitatea finala a algoritmului va fi $O(N^2^*logN)$ deoarece, in cazul cel mai defavorabil, toate celulele sunt turn (un exemplu este cand matricea este piramidala) si in consecinta toate celulele vor fi introduse si scoase din heap necesitand logN pentru fiecare operatie. Aflarea componentelor conexe va necesita $O(N^2^)$ timp in total fiindca o celula va fi selectata o singura data intr-o componenta conexa si va fi accesata de maxim 4 ori de algoritmul $FILL$. Ca detalii de implementare, programatorii in $C++$ pot folosi cozile de prioritati din $STL$ ({$priority_queue$} ce se gaseste in headerul {$<queue>$}) pentru a reduce din complexitatea implementarii. Totusi, trebuie acordata atentie utilizarii acestora deoarece este posibil ca sursa sa depasesca timpul de executie.

h2. Naptime

$A{~i,j,0~} = max(A{~i-1,j,0~}, A{~i-1,j,1~})$
Am redus complexitatea la $O(N*B)$ si memoria la $O(N)$, o imbunatatire substantiala.

Deoarece sirul este circular, putem rezolva problema aplicand de N$$ ori dinamica de mai sus considerand sirul liniar si alegand fiecare pozitie ca fiind pozitia initiala, dar aceasta solutie depaseste cu mult limita de timp pe cazul cel mai defavorabil. Totusi, aceasta idee ar fi adus $10$ teste din cele $14$. Cu un mic truc, si anume alegerea aleatorie a pozitiei de start cat timp nu s-a depasit timpul de executie, s-ar mai fi putut obtine inca $2$ teste, in total $12$ (desi aceasta rezolvare nu obtine solutia optima pe testele foarte mari).

Deoarece sirul este circular, putem rezolva problema aplicand de $N$ ori dinamica de mai sus considerand sirul liniar si alegand fiecare pozitie ca fiind pozitia initiala, dar aceasta solutie depaseste cu mult limita de timp pe cazul cel mai defavorabil. Totusi, aceasta idee ar fi adus $10$ teste din cele $14$. Cu un mic truc, si anume alegerea aleatorie a pozitiei de start cat timp nu s-a depasit timpul de executie, s-ar mai fi putut obtine inca $2$ teste, in total $12$ (desi aceasta rezolvare nu obtine solutia optima pe testele foarte mari).

Putem scapa de faptul ca sirul este circular mult mai elegant, aplicand de 2 ori dinamica: odata cum am zis mai sus (acoperind cazul cand pozitiile $N$ si $1$ nu sunt in aceeasi secventa de pozitii consecutive) si inca odata fortand sa existe o secventa de utilitati aleasa care contine pozitiile $N$ si $1$. A doua dinamica se poate obtine exact ca mai sus, aplicand aceeasi idee doar ca se initializeaza $A{~1,1,1~}=U{~1~}$ in loc de 0, si apoi pentru fiecare $i$ se verifica rezultatul curent cu $max(A{~i,B-(N-i),0~}, A{~i,B-(N-i),1~} + suma U{~i+2~}...U{~N~})$. Pentru a se incadara in limita de 0.3s trebuie acordata o mare grija la implementare, de exemplu, optimizand dinamica de mai sus de la $2*N$ memorie (ultimele doua linii din matricea $A$) la doar $N$ pastrand doar ultima linie si parcurgand indicele $j$ descrescator.