(Creat de ==user(user="silviug" type="tiny")== la data de _2004-12-18_ categoria _Competitii_, autor(i) _Silviu Ganceanu_)

"Setul de probleme": pe marginea caruia voi discuta in urmatoarele randuri se afla disponibil in sectiunea download impreuna cu datele de test si rezultatele finale ale concursului (cei care nu stiu setul de probleme si vor sa citeasca articolul sunt rugati sa parcurga mai intai textele problemelor).

"Setul de probleme":http://info.devnet.ro/download.php?page=cat&cat=30 pe marginea caruia voi discuta in urmatoarele randuri se afla disponibil in sectiunea download impreuna cu datele de test si rezultatele finale ale concursului (cei care nu stiu setul de probleme si vor sa citeasca articolul sunt rugati sa parcurga mai intai textele problemelor).

Voi incepe prin cateva observatii in legatura cu evolutia concurentilor din Romania in acest concurs. Asadar un clasament (neoficial) alcatuit intre acestia ar arata in urmatorul mod:

h2. Skiarea

Problema se poate rezolva utilizand cunostinte de teoria grafurilor. Mai intai se contruiesc componentele conexe ale fiecarei celule printr-un algoritm de tipul FLOOD FILL. Prin componenta conexa intelegem set de celule din matrice cu aceeasi valoarea si care indeplineste propietatea ca intre oricare doua celule exista drum (dupa regulile din enunt). Odata aflate aceste componente conexe se construieste un graf asociat lor in urmatorul mod:

Problema se poate rezolva utilizand cunostinte de teoria grafurilor. Mai intai se contruiesc componentele conexe ale fiecarei celule printr-un algoritm de tipul {$FLOOD FILL$}. Prin componenta conexa intelegem set de celule din matrice cu aceeasi valoarea si care indeplineste propietatea ca intre oricare doua celule exista drum (dupa regulile din enunt). Odata aflate aceste componente conexe se construieste un graf asociat lor in urmatorul mod:

* fiecare componenta conexa are asociat un nod

* intre doua noduri x si y exista drum daca componenta conexa asociata lui x este "vecina" cu componenta conexa a lui y (este usor de intuit ce inseamna "vecina") si daca valoarea celulelor din x este mai mare decat valoarea celulelor din y.

* intre doua noduri $x$ si $y$ exista drum daca componenta conexa asociata lui $x$ este "vecina" cu componenta conexa a lui $y$ (este usor de intuit ce inseamna "vecina") si daca valoarea celulelor din $x$ este mai mare decat valoarea celulelor din {$y$}.

Graful astfel construit este aciclic (acesta se demostreaza usor). In acest graf aflam nodurile in care nu intra nici o muchie - noduri "sursa" - (fie numarul lor P) si toate nodurile din care nu iese nici o muchie - noduri "destinatie" - (fie numarul lor Q). Solutia pentru problema noastra va fi:

Graful astfel construit este aciclic (acesta se demostreaza usor). In acest graf aflam nodurile in care nu intra nici o muchie - noduri "sursa" - (fie numarul lor {$P$}) si toate nodurile din care nu iese nici o muchie - noduri "destinatie" - (fie numarul lor {$Q$}). Solutia pentru problema noastra va fi:

* maxim dintre P si Q, daca graful are doua sau mai multe noduri
* 0, daca graful are un singur nod.

* maxim dintre $P$ si {$Q$}, daca graful are doua sau mai multe noduri
* {$0$}, daca graful are un singur nod.

Toate cele trei etape (FLOOD FILL-ul, construirea grafului, aflarea nodurilor "sursa" si "destinatie") se pot realiza in O(N*M) operatii utilizand O(N*M) spatiu de memorie. Mare atentie insa: nici unul dintre pasi nu trebuie realizat recursiv!! (pentru ca altfel se iese din segmentul de stiva pe testele mari).

Toate cele trei etape ({$FLOOD FILL-ul$}, construirea grafului, aflarea nodurilor "sursa" si "destinatie") se pot realiza in $O(N*M)$ operatii utilizand $O(N*M)$ spatiu de memorie. Mare atentie insa: nici unul dintre pasi nu trebuie realizat recursiv!! (pentru ca altfel se iese din segmentul de stiva pe testele mari).

References
 
Visible links
1. http://info.devnet.ro/download.php?page=cat&cat=30
2. http://info.devnet.ro/download.php?page=cat&cat=24