Acest set de probleme a fost considerat unul dintre cele mai grele, daca nu cel mai greu, de pana acum. Problemele au fost intr-adevar dure cu atat mai mult cu cat timpul de lucru a fost mic (3 ore). In ciuda acestui fapt concurentii din Romania s-au comportat bine, concursul marcand primul succes de pe anul acesta al tarii noastre: locul 5 obtinut de Adrian Vladu.

Desi rezultatele i-au determinat pe antrenorii americani sa considere setul de probleme cel mai greu de pana acum, pentru multi dintre elevii Romaniei problemele nu au fost in totalitate noi: cover a fost propusa (sub o forma un pic diferita) la CEOI, o varinta ceva mai blanda a problemei juice (cu limite mai mici) am putut vedea si in finala rundei .Campion de anul trecut iar ideea de rezolvare pentru naptime nu era noua (o problema din concursul @"Stelele Informaticii"@ de anul trecut se pare ca semana mult cu aceasta).

Desi rezultatele i-au determinat pe antrenorii americani sa considere setul de probleme cel mai greu de pana acum, pentru multi dintre elevii Romaniei problemele nu au fost in totalitate noi: cover a fost propusa (sub o forma un pic diferita) la CEOI, o varinta ceva mai blanda a problemei juice (cu limite mai mici) am putut vedea si in finala rundei .Campion de anul trecut iar ideea de rezolvare pentru naptime nu era noua (o problema din concursul $"Stelele Informaticii"$ de anul trecut se pare ca semana mult cu aceasta).

Cu toate aceastea problemele au fost deosebit de dificile necesitand concentrare maxima. Rezultatele elevilor din Romania s-au imbunatatit semnificativ fata de concursul precedent, acestia obtinand locuri mai bune. O parte din succesul acestora indraznesc sa o pun si pe seama faptului ca problema cea mai grea din concurs era cunoscuta la noi in tara. Avem astfel urmatorul clasament:

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:

*.*.
 
.***
 
***.
 
..*.

$ *.*. $
$ .*** $
$ ***. $
$ ..*. $

Iata cum vom construi prima multime a grafului bipartit (vom pune numarul nodului din graf corespunzator fiecarei celule):

1.2.
 
.333
 
444.
 
..5.

$ 1.2. $
$ .333 $
$ 444. $
$ ..5. $

A doua multime a grafului bipartit va arata astfel (nodurile vor fi numerotate incepand tot cu 1):

1.2.
 
.324
 
532.
 
..2.

$ 1.2. $
$ .324 $
$ 532. $
$ ..2. $

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:
 
 

$(1, 1) (2, 2) (3, 3) (3, 2) (3, 4) (4, 5) (4, 3) (4, 2) (5, 2)$

PAS 1: Construirea grafului bipartit

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:

PAS 2: Aflarea cuplajului maximal

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