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:
@*.*.@

  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