h1. Usaco ianuarie 2005, divizia GOLD
(Creat de '_silviug_':user/silviug la data de _2005-03-03_ categoria _Competitii_, autor(i) _Silviu Ganceanu, Mircea Pasoi_)
(Categoria _Competitii_, autor(i) _Silviu Ganceanu, Mircea Pasoi_)
==Include(page="template/raw")==
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).
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:
table(example). | 1. | Adrian Vladu | 958 puncte |
| 2. | Sorin Stancu-Mara | 703 puncte |
| 3. | Mircea Pasoi | 700 puncte |
| 4. | Andrei Teodorescu | 640 puncte |
| 5. | Dan-Ionut Fechete | 547 puncte |
| 6. | Adrian Diaconu | 502 puncte |
table. |_. 1. | Adrian Vladu | $958$ puncte |
|_. 2. | Sorin Stancu-Mara | $703$ puncte |
|_. 3. | Mircea Pasoi | $700$ puncte |
|_. 4. | Andrei Teodorescu | $640$ puncte |
|_. 5. | Dan-Ionut Fechete | $547$ puncte |
|_. 6. | Adrian Diaconu | $502$ puncte |
Restul concurentilor au obtinut punctaje frumoase dar mai mici de 400 de puncte. Sunt de remarcat comportarile bune de pana acum ale lui Andrei Teodorescu care reuseste sa se "tina" de mult mai titratii elevi ai Romaniei care au deja in palmares cel putin o medalie internationala.
Restul concurentilor au obtinut punctaje frumoase dar mai mici de $400$ de puncte. Sunt de remarcat comportarile bune de pana acum ale lui Andrei Teodorescu care reuseste sa se "tina" de mult mai titratii elevi ai Romaniei care au deja in palmares cel putin o medalie internationala.
Setul de probleme, impreuna cu testele si clasamentul, se gaseste in cadrul "sectiunii download":http://info.devnet.ro/download.php?page=cat&cat=33 . In continuare vom prezenta solutiile:
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:
@*.*.@
@.***@
@***.@
@..*.@
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:
* PAS 1: Construirea grafului bipartit$
* PAS 2: Aflarea cuplajului maximal$
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):
1. guards (CEOI 2002)
2. knigths (Baltica 2001) - in solutia oficiala a acestei probleme gasiti mai multe informatii despre notiunea de cuplaj maximal intr-un graf bipartit si problemele inrudite
3. Problema Paznici din runda a patra a concursului Algoritmus (gasiti pe pagina si explicatia solutiei) [2]http://algoritmus.org/probleme/Probleme_Runda04.php
4. [3]http://acm.timus.ru/problem.aspx?space=1&num=1106
5. [4]http://acm.sgu.ru/problem.php?contest=0&problem=234
6. [5]http://acm.sgu.ru/problem.php?contest=0&problem=210
7. [6]http://acm.sgu.ru/problem.php?contest=0&problem=218
8. [7]http://online-judge.uva.es/p/v107/10735.html
9. [8]http://online-judge.uva.es/p/v108/10804.html
10. [9]http://online-judge.uva.es/board/viewtopic.php?t=7462
# $guards (CEOI 2002)$
# $knigths (Baltica 2001)$ - in solutia oficiala a acestei probleme gasiti mai multe informatii despre notiunea de cuplaj maximal intr-un graf bipartit si problemele inrudite
# Problema "Paznici":http://algoritmus.org/probleme/probleme_runda04.php din runda a patra a concursului Algoritmus (gasiti pe pagina si explicatia solutiei)
# "http://acm.timus.ru/problem.aspx?space=1&num=1106":http://acm.timus.ru/problem.aspx?space=1&num=1106
# "http://acm.sgu.ru/problem.php?contest=0&problem=234":http://acm.sgu.ru/problem.php?contest=0&problem=234
# "http://acm.sgu.ru/problem.php?contest=0&problem=210":http://acm.sgu.ru/problem.php?contest=0&problem=210
# "http://acm.sgu.ru/problem.php?contest=0&problem=218":http://acm.sgu.ru/problem.php?contest=0&problem=218
# "http://online-judge.uva.es/p/v107/10735.html":http://online-judge.uva.es/p/v107/10735.html
# "http://online-judge.uva.es/p/v108/10804.html":http://online-judge.uva.es/p/v108/10804.html
# "http://online-judge.uva.es/board/viewtopic.php?t=7462":http://online-judge.uva.es/board/viewtopic.php?t=7462
Mentionez ca problema 8 m-a impresionat in mod placut fiind una dintre cele mai frumoase probleme pe care le-am intalnit in ultimele cateva luni.
Juice
Fie A(i, j) inaltimea blocului aflat in pozitia (i, j). Aflam inaltimea maxima la care poate urca nivelul sucului in fiecare celula. Daca notam aceasta inaltime cu B(i, j) solutia problemei va fi suma( B(i, j) - A(i, j) ).
Vom numi celula turn o celula (i, j) care are propietatea ca B(i, j) = A(i, j) (nu putem pune suc in ea pentru ca ar curge in afara matricei). Componenta conexa a unei celule turn (i, j) este compusa din acele celule (x, y) pentru care avem B(x, y) = A(i, j). Definim inaltimea componentei conexe ca fiind inaltimea comuna a tuturor celulelor componente. Facem urmatoarele observatii utile in rezolvarea problemei:
1. Celulele de pe marginea matricei sunt celule turn
2. Celula (x, y) devine celula turn daca este vecina unei celule (i, j) ce face parte dintr-o componenta conexa si are propietatea ca B(i, j) < A(x, y).
h2. Juice
Incet, incet se contureaza solutia problemei observand ca, pentru a declara o celula ca fiind turn, trebuie sa aflam componentele conexe ale celulelor turn mai joase decat ea. Acest lucru ne aduce la ideea de procesa aceste celule turn in ordinea inaltimii lor afland pentru fiecare componenta conexa corespunzatoare. In acelasi timp aflam si celule ce devin turn si sunt mai inalte. Pentru aceasta utilizam o coada de prioritati (un heap) in care pastram toate celule turn neprocesate inca ordonate descrescator dupa inaltime. Ajungem astfel la nimic altceva decat un algoritm de tip FILL modificat corespunzator cerintelor acestei probleme. Iata o descriere a acestuia:
Fie $A{~i,j~}$ inaltimea blocului aflat in pozitia $(i, j)$. Aflam inaltimea maxima la care poate urca nivelul sucului in fiecare celula. Daca notam aceasta inaltime cu B{~i,j~} solutia problemei va fi $suma( B{~i,j~} - A{~i,j~} )$.
Vom numi celula turn o celula $(i, j)$ care are propietatea ca $B{~i,j~} = A{~i,j~}$ (nu putem pune suc in ea pentru ca ar curge in afara matricei). Componenta conexa a unei celule turn $(i, j)$ este compusa din acele celule $(x, y)$ pentru care avem $B{~x,y~} = A{~i,j~}$. Definim inaltimea componentei conexe ca fiind inaltimea comuna a tuturor celulelor componente. Facem urmatoarele observatii utile in rezolvarea problemei:
# Celulele de pe marginea matricei sunt celule turn
# Celula $(x, y)$ devine celula turn daca este vecina unei celule $(i, j)$ ce face parte dintr-o componenta conexa si are propietatea ca $B{~i,j~} < A{~x,y~}$.
PAS 1: Se introduc in coada de prioritati
pozitiile de pe margine
Incet, incet se contureaza solutia problemei observand ca, pentru a declara o celula ca fiind turn, trebuie sa aflam componentele conexe ale celulelor turn mai joase decat ea. Acest lucru ne aduce la ideea de procesa aceste celule turn in ordinea inaltimii lor afland pentru fiecare componenta conexa corespunzatoare. In acelasi timp aflam si celule ce devin turn si sunt mai inalte. Pentru aceasta utilizam o coada de prioritati (un heap) in care pastram toate celule turn neprocesate inca ordonate descrescator dupa inaltime. Ajungem astfel la nimic altceva decat un algoritm de tip $FILL$ modificat corespunzator cerintelor acestei probleme. Iata o descriere a acestuia:
==code(cpp) |
PAS 1: Se introduc in coada de prioritati pozitiile de pe margine
PAS 2: Cat timp heapul nu este gol:
* se selecteaza celula turn cea mai joasa
* se afla componenta conexa a acesteia
* se introduc in coada de prioritati
celulele vecine cu componenta conexa construita
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 (pririority_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.
Naptime
Vom incerca sa rezolvam problema, ignorand la inceput faptul ca sirul este circular. Astfel, problema se transforma intr-una relativ usoara, abordabila cu programare dinamica. O prima incercare ar fi sa realizam o astfel de rezolvare: A(i, j) = utilitatea de somn maxima care se poate obtine alegand j perioade din primele i.
Relatia de recurenta care se obtine este A(i, j)=max(A(i-k, j-k)+suma U[i-k+2]...U[i]) unde U este vectorul de utilitati. Din pacate aceasta abordare are dezavantajul ca are complexitatea de timp O(N*B^2) si de memorie O(N*B), neincadrandu-se nici in timp si nici in spatiu de memorie. Astfel, vom incerca sa imbunatatim aceasta dinamica modificand un pic semnificatia matricei A bazandu-ne pe faptul ca alegerea unei secvente continue de perioade aduca ca utilitate suma lor, mai putin prima perioada folosita:
A(i, j, 1) = utilitatea de somn maxima care se poate obtine alegand j perioade din primele i si ultima perioada folosita sa fie j
A(i, j, 0) = utilitatea de somn maxima care se poate obtine alegand j perioade din primele i si ultima perioada folosita sa NU fie j
* se introduc in coada de prioritati celulele vecine cu componenta conexa construita,
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.
h2. Naptime
Vom incerca sa rezolvam problema, ignorand la inceput faptul ca sirul este circular. Astfel, problema se transforma intr-una relativ usoara, abordabila cu programare dinamica. O prima incercare ar fi sa realizam o astfel de rezolvare: $A{~i,j~}$ = utilitatea de somn maxima care se poate obtine alegand $j$ perioade din primele $i$.
Relatia de recurenta care se obtine este $A{~i,j~}=max(A{~i-k,j-k~}+suma U{~i-k+2~}...U{~i~})$ unde $U$ este vectorul de utilitati. Din pacate aceasta abordare are dezavantajul ca are complexitatea de timp $O(N*B^2^)$ si de memorie $O(N*B)$, neincadrandu-se nici in timp si nici in spatiu de memorie. Astfel, vom incerca sa imbunatatim aceasta dinamica modificand un pic semnificatia matricei A bazandu-ne pe faptul ca alegerea unei secvente continue de perioade aduca ca utilitate suma lor, mai putin prima perioada folosita:
$A{~i,j,0~}$ = utilitatea de somn maxima care se poate obtine alegand $j$ perioade din primele $i$ si ultima perioada folosita sa fie $j$
$A{~i,j,1~}$ = utilitatea de somn maxima care se poate obtine alegand $j$ perioade din primele $i$ si ultima perioada folosita sa *NU* fie $j$
Obtinem relatiile de recurenta:
A(i, j, 1) = max(A(i-1, j-1, 1) + U[i], A(i-1, j-1, 0))
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).
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.
References
Visible links
2. http://algoritmus.org/probleme/probleme_runda04.php
3. http://acm.timus.ru/problem.aspx?space=1&num=1106
4. http://acm.sgu.ru/problem.php?contest=0&problem=234
5. http://acm.sgu.ru/problem.php?contest=0&problem=210
6. http://acm.sgu.ru/problem.php?contest=0&problem=218
7. http://online-judge.uva.es/p/v107/10735.html
8. http://online-judge.uva.es/p/v108/10804.html
9. http://online-judge.uva.es/board/viewtopic.php?t=7462
$A{~i,j,1~} = max({~i-1,j-1,1~} + U{~i~}, A{~i-1,j-1,0~})$
$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).
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.
