Diferente pentru usaco-ian-2005-divizia-gold intre reviziile #20 si #21

Nu exista diferente intre titluri.

Diferente intre continut:

==
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

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.