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 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.
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, 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
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.
$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).
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.
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
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.
