Diferente pentru deque-si-aplicatii intre reviziile #111 si #140

Nu exista diferente intre titluri.

Diferente intre continut:

* 'Probleme suplimentare':deque-si-aplicatii#probleme-suplimentare
* 'Bibliografie':deque-si-aplicatii#bibliografie
În acest articol voi prezenta o structură de date liniară de tip listă numită _deque_. Aceasta nu este una complexă, în schimb se va dovedi foarte folositoare. După o scurtă prezentare, mă voi axa pe o serie de aplicaţii care vor arăta surprinzătoarea sa utilitate în locurile unde am fi crezut că nu se mai poate face nimic pentru a reduce complexitatea algoritmului.
În acest articol voi prezenta o structură de date liniară de tip listă numită _deque_. Aceasta nu este una complexă, în schimb se va dovedi foarte folositoare. După o scurtă prezentare, mă voi axa pe o serie de aplicaţii care vor arăta surprinzătoarea sa utilitate în locurile unde am fi crezut că nu se mai poate face nimic pentru a reduce complexitatea algoritmului. De menţionat că primul care a folosit această noţiune a fost Donald Knuth în lucrarea "_The Art of Computer Programming_" ({_Volume 1: Fundamental Algorithms, Third Edition_}) din 1997.
h2(#descriere). Descrierea structurii
h3. Soluţie:
Soluţia simplă constă în procesarea tuturor perechilor de numere care se găsesc pe poziţii cu diferenţa în modul mai mică sau egală decât $D$.
Soluţia naivă constă în procesarea tuturor perechilor de numere care se găsesc pe poziţii cu diferenţa în modul mai mică sau egală decât $D$.
== code(cpp) |
Algoritmul este:
Sfârşit.
==
Complexitatea algoritmului este $O(N^2^)$, dar care pentru limitele problemei este enorm.
Complexitatea algoritmului este $O(N^2^)$, dar pentru limitele problemei este enorm de mare.
Din pseudocodul de mai sus se vede că pentru un indice $i$ fixat, iterăm cu un alt indice $j$ pentru a găsi diferenţa maximă în modul dintre $S[i]$ şi un alt număr din intervalul $[i - D, i]$. Însă, diferenţa dintre cel mai mare număr şi cel mai mic număr este cel puţin la fel de bună decât rezultatul anterior. Astfel, pentru indicele $i$ fixat succesiv cu $1$, $2$, .., $N$, considerăm secvenţa $[i - D, i]$ în care determinăm valoarea maximă şi valoarea minimă iar diferenţa lor o comparăm cu rezultatul cel mai bun obţinut până în acel moment. Dacă considerăm o secvenţă de lungime mai scurtă, atunci este posibil să pierdem din soluţii. Un caz este când cea mai mică şi cea mai mare dintre valori se găsesc pe poziţiile $i - D$, respectiv $i$.
Din pseudocodul de mai sus se vede că pentru un indice $i$ fixat, iterăm cu un alt indice $j$ pentru a găsi diferenţa maximă în modul dintre $S[i]$ şi un alt număr din intervalul $[i - D, i]$. Însă, diferenţa dintre cel mai mare număr şi cel mai mic număr este cel puţin la fel de bună ca rezultatul de la $j$-ul anterior. Astfel, pentru indicele $i$ fixat succesiv cu $1$, $2$, .., $N$, considerăm secvenţa $[i - D, i]$ în care determinăm valoarea maximă şi valoarea minimă, iar diferenţa lor o comparăm cu rezultatul cel mai bun obţinut până în acel moment.
Pentru fixarea ideii, să urmărim cum putem determina eficient valoarea maximă din fiecare secvenţă $[i - D, i]$.
# Dacă $S[i{~1~}] ≤ S[i{~2~}]$ atunci, cât timp cei doi indici vor fi în intervale de tipul $[i - D, i]$, valoarea de pe poziţia $i{~2~}$ va fi întotdeauna preferată valorii de pe poziţia $i{~1~}$. Când se ajunge la un interval care nu-l mai conţine pe $i{~1~}$, $i{~2~}$ rămâne în continuare preferat.
# Dacă $S[i{~1~}] > S[i{~2~}]$ atunci şi valoarea de pe poziţia $i{~1~}$ şi cea de pe poziţia $i{~2~}$ sunt candidate la maxim, la momentul curent sau în viitor.
Cu această observaţie deducem că într-o secvenţă $[i - D, i]$ vom avea un şir strict descrescător de numere: $T{~i~} = S[i{~1~}] &gt; S[i{~2~}] &gt; ... &gt; S[i{~K~}]$, unde $S[i{~1~}]$ elimină toate elementele $S[j]$, cu $S[j] < S[i{~1~}]$ şi $i - D &le; j &lt; i{~1~}$, $S[i{~2~}]$ elimină toate elementele $S[j]$, cu $S[j] < S[i{~2~}]$ şi $i - D &le; j &lt; i{~2~}, j != i{~1~}$ dar fără poziţia $i{~1~}$ ş.a.m.d.
Şirul $T{~i~}$ are următoarele proprietăţi:
Cu această observaţie deducem că într-o secvenţă $[i - D, i]$ vom avea un şir strict descrescător de numere: $T{~i~} = S[i{~1~}] &gt; S[i{~2~}] &gt; ... &gt; S[i{~K~}]$, unde $S[i{~1~}]$ elimină toate elementele $S[j]$, cu $S[j] &le; S[i{~1~}]$ şi $i - D &le; j &lt; i{~1~}$, $S[i{~2~}]$ elimină toate elementele $S[j]$, cu $S[j] &le; S[i{~2~}]$ şi $i{~1~} &lt; j &lt; i{~2~}$, $S[i{~3~}]$ elimină toate elementele $S[j]$, cu $S[j] &le; S[i{~3~}]$ şi $i{~2~} &lt; j &lt; i{~3~}$ ş.a.m.d. De reţinut este că niciuna dintre valorile de pe poziţiile eliminate nu poate fi maximă, motiv pentru care le-am putut elimina. Şirul $T{~i~}$ are următoarele proprietăţi:
* se termină pe poziţia curentă, adică are loc egalitatea $i{~K~} = i$ întrucât poziţia $i$ nu va fi eliminată de nicio altă poziţie;
* valoarea căutată, adică maximul dintre numerele din secvenţă, se găseşte pe prima poziţie.
Când vom avansa la secvenţa următoare, $[i - D + 1, i + 1]$, vom forma şirul $T{~i+1~}$ ştergând din indicii $i{~1~}$, $i{~2~}$... atâta timp cât nu se găsesc în intervalul curent şi vom şterge din poziţiile $i{~K~}$, $i{~K-1~}$... cât timp $S[i + 1] &gt; S[i{~K~}]$, $S[i + 1] &gt; S[i{~K-1~}]$... adică cât timp se îndeplineşte primul punct din observaţia anterioară.
Când vom avansa la secvenţa următoare, $[i - D + 1, i + 1]$, vom forma şirul $T{~i+1~}$ ştergând din indicii $i{~1~}$, $i{~2~}$ ... atâta timp cât nu se găsesc în intervalul curent şi vom şterge din poziţiile $i{~K~}$, $i{~K-1~}$ ... cât timp $S[i + 1] &ge; S[i{~K~}]$, $S[i + 1] &ge; S[i{~K-1~}]$ ...
Şirul $T{~i~}$ poate fi păstrat prin intermediul şirului de indici $i{~1~} &lt; i{~2~} &lt; ... &lt; i{~K~}$ care este continuu iar operaţiile de mai sus se efectuează doar pe la cele două capete. Rezultă că şirul poate fi implementat cu ajutorul unui deque.
Şirul $T{~i~}$ poate fi păstrat prin intermediul şirului de indici $i{~1~} &lt; i{~2~} &lt; ... &lt; i{~K~}$. Operaţiile pe acest şir se efectuează doar pe la cele două capete, aşadar poate fi implementat cu ajutorul unui $deque$.
Pentru $S[] = {5, 9, 4, 7, 4, 1}$ şi $D = 3$ obţinem următoarele stări ale unui deque:
* <tex> \langle \widehat{5\ [1]} \rangle; </tex>
* <tex> \langle 5\ [1] \rangle \Leftarrow 9\ [2] </tex> de unde se obţine <tex> \langle \widehat{9\ [2]} \rangle; </tex>
* <tex> \langle 9\ [2] \rangle \Leftarrow 4\ [3] </tex> de unde se obţine <tex> \langle \widehat{9\ [2]},\ 4\ [3] \rangle; </tex>
* <tex> \langle 9\ [2],\ 4\ [3] \rangle \Leftarrow 7\ [4] </tex> de unde se obţine <tex> \langle \widehat{9\ [2]},\ 7\ [4] \rangle; </tex>
* <tex> 9\ [2] \Leftarrow \langle 7\ [4] \rangle \Leftarrow 4\ [5] </tex> de unde se obţine <tex> \langle \widehat{7\ [4]},\ 4\ [5] \rangle; </tex>
* <tex> \langle 7\ [4],\ 4\ [5] \rangle \Leftarrow 1\ [6] </tex> de unde se obţine <tex> \langle \widehat{7\ [4]},\ 4\ [5],\ 1\ [6] \rangle; </tex>
* <tex> \langle \widehat{5\ [1]} \rangle </tex>;
* <tex> \langle 5\ [1] \rangle \Leftarrow 9\ [2] </tex> de unde se obţine <tex> \langle \widehat{9\ [2]} \rangle </tex>;
* <tex> \langle 9\ [2] \rangle \Leftarrow 4\ [3] </tex> de unde se obţine <tex> \langle \widehat{9\ [2]},\ 4\ [3] \rangle </tex>;
* <tex> \langle 9\ [2],\ 4\ [3] \rangle \Leftarrow 7\ [4] </tex> de unde se obţine <tex> \langle \widehat{9\ [2]},\ 7\ [4] \rangle </tex>;
* <tex> 9\ [2] \Leftarrow \langle 7\ [4] \rangle \Leftarrow 4\ [5] </tex> de unde se obţine <tex> \langle \widehat{7\ [4]},\ 4\ [5] \rangle </tex>;
* <tex> \langle 7\ [4],\ 4\ [5] \rangle \Leftarrow 1\ [6] </tex> de unde se obţine <tex> \langle \widehat{7\ [4]},\ 4\ [5],\ 1\ [6] \rangle </tex>;
Cum fiecare indice din $1$, $2$, .., $N$ trece cel mult o dată prin deque, complexitatea finală este $O(N)$.
Cum fiecare indice din $1$, $2$, ..., $N$ este adăugat şi şters cel mult o dată din deque, complexitatea finală este $O(N)$.
h2(#problema-3). 3. 'Şir':problema/sir
bq. Se dă un şir $S$ de numere întregi de lungime $N$. Se cere să se găsească secvenţa de lungime maximă cuprinsă între $X$ şi $Y$ astfel încât $MAX - MIN &le; Z$, unde $MAX$ este maximul dintre toate numerele întregi din secvenţă iar $MIN$ minimul dintre acestea. Secvenţa soluţie va fi cea cu poziţia de început maximă dintre toate secvenţele de lungime maximă.
bq. Se dă un şir $S$ de numere întregi de lungime $N$. Se cere să se găsească secvenţa de lungime maximă cuprinsă între $X$ şi $Y$ astfel încât $MAX - MIN &le; Z$, unde $MAX$ este maximul dintre toate numerele întregi din secvenţă, iar $MIN$ minimul dintre acestea. Secvenţa soluţie va fi cea cu poziţia de început maximă dintre toate secvenţele de lungime maximă.
Restricţii: $3 &le; N &le; 100 000$, $1 &le; X &le; Y &le; N$, $0 &le; Z &le; 30 000$.
h3. Soluţie:
Voi prezenta mai jos o rafinare a soluţiei în trei paşi.
Prima rezolvare se găseşte uşor, deoarece nu facem decât să urmărim textul: pentru fiecare poziţie $i$ fixată ({$i$} ia valorile $1$, $2$, .., $N$ succesiv) vom determina pentru aceasta secvenţa cerută, adică vom plimba un $j$ între poziţiile $i - Y$ şi $i - X$. Pentru un interval $(j, i]$ vom determina $MAX$ şi $MIN$ în $O(log{~2~}N)$ cu un arbore de intervale, iar daca diferenţa dintre acestea nu depăşeşte $Z$ vom compara cu soluţia finală. Complexitatea finală va fi $O(N * (Y - X) * log{~2~}Y)$.
Prima rezolvare se găseşte uşor, deoarece nu facem decât să urmărim textul: pentru fiecare poziţie $i$ fixată ({$i$} ia valorile $1$, $2$, ..., $N$ succesiv) vom considera toate secvenţele candidate la rezultatul final, adică vom plimba un $j$ între poziţiile $i - Y + 1$ şi $i - X + 1$. Pentru un interval $[j, i]$ vom determina $MAX$ şi $MIN$ în $O(log N)$ cu un arbore de intervale, iar dacă diferenţa dintre acestea nu depăşeşte $Z$ vom compara rezultatul cu cel obţinut nă în acel moment. Complexitatea finală va fi $O(N * (Y - X) * log N)$.
 presupunem că pentru poziţia curentă $i$, l-am găsit pe $j$ cât mai mic cuprins între $i - Y$ şi $i - X$ astfel încât secvenţa $(j, i]$ este candidată la soluţie. Ce proprietăţi are $j$?
Cum se cere secvenţa de lungime maximă, pentru fiecare poziţie $i$ trebuie găsit indicele $j$ cât mai mic cuprins între $i - Y + 1$ şi $i - X + 1$ astfel încât secvenţa $[j, i]$ să fie candidată la soluţie. Ce proprietăţi are indicele $j$?
* $i - Y &le; j &le; i - X$ şi $MAX - MIN &le; Z$;
* dacă îl incrementăm pe $j$ la $j + 1$ atunci dacă $j &le; i - X$ cu siguranţă $MAX - MIN &le; Z$ şi astfel soluţia va fi mai scurtă;
* dacă îl decrementăm pe $j$, atunci ori $j < i - Y$ ori $MAX - MIN > Z$;
* dacă îl incrementăm pe $i$ la $i + 1$, atunci se poate întâmpla ca $j < i - Y$; cum $MAX$ nu poate decât să crească, iar $MIN$ decât să scadă, se mai poate de asemenea întâmpla ca $MAX - MIN > Z$.
* $i - Y + 1 &le; j &le; i - X + 1$ şi $MAX - MIN &le; Z$;
* având $i$-ul fixat, dacă trecem de la $j$ la $j + 1$, maximul poate scădea, iar minimul poate creşte, dar în mod sigur diferenţa lor va rămâne mai mică sau egală cu $Z$; soluţia astfel obţinută este mai scurtă, deci nu îmbunătăţeşte soluţia obţinută anterior.
* dacă trecem de la $i$ la $i + 1$, cel mai mic $j$ găsit la pasul anterior poate ori să nu corespundă celor două restricţii (caz în care îl incrementăm cât timp $j < i - Y + 2$ sau $MAX - MIN > Z$), ori să corespundă şi atunci este cel mai mic care să respecte proprietăţile pentru $i + 1$.
Datorită proprietăţilor de mai sus, când trecem de la $i$ la $i + 1$, valoarea lui $j$ nu poate decât să crească cât timp $j < i - Y$ sau $MAX - MIN > Z$ şi $j$ nu a depăşit poziţia $i - X$. Pentru determinarea lui $MAX$, respectiv lui $MIN$ se poate folosi un arbore de intervale. Complexitatea finală va fi $O(N * log{~2~}(Y))$.
Pentru determinarea lui $MAX$, respectiv lui $MIN$ pe fiecare interval $[j, i]$, se poate folosi un arbore de intervale. Complexitatea finală va fi $O(N * log N)$.
Cu cei doi indici $i$ şi $j$ vom accesa fiecare element din cele $N$ de cel mult $2$ ori, o dată cu $i$ şi o da cu $j$. Să vedem cum putem îmbunătăţi complexitatea $O(log{~2~}Y)$ pentru determinarea maximului şi minimului.
 vedem cum putem îmbunătăţi complexitatea $O(log N)$ pentru determinarea maximului şi minimului. Mai jos vom vedea algoritmul pentru a-l calcula pe $MAX$, cazul lui $MIN$ fiind similar. Observaţia care ne ajută în multe probleme pentru reducerea complexităţii de la $O(log N)$ la $O(1)$ este, asemănător problemei precedente, următoarea:
Pentru fixarea ideilor să urmărim cum îl vom calcula pe $MAX$. Observaţia care ne ajută în multe probleme pentru reducerea complexităţii de la $O(log{~2~}N)$ la $O(1)$ amortizat este următoarea:
_Observaţie_: Fie $[j, i]$ un interval de interes şi $i{~1~}$ şi $i{~2~}$ doi indici astfel încât $j &le; i{~1~} < i{~2~} &le; i$. Atunci, dacă $S[i{~1~}] < S[i{~2~}]$ poziţia $i{~2~}$ va fi întotdeauna preferată poziţiei $i{~1~}$ atâta timp cât cele două poziţii vor fi în acelaşi interval de interes. Aşadar putem renunţa la $i{~1~}$ pentru etapele următoare, eliminându-l. Dacă, însă, $S[i{~1~}] &ge; S[i{~2~}]$, atunci poziţia $i{~1~}$ "va umbri" poziţia $i{~2~}$ atâta timp cât cele două poziţii vor fi în intervalul de forma $[j, i]$. În schimb, când $i{~1~}$ va fi eliminat, $i{~2~}$ are şansa să fie un candidat la $MAX$ dintre restul elementelor de la dreapta sa. În acest caz, vom păstra ambele poziţii şi pentru paşii următori.
_Observaţie_: Fixăm $i{~1~}$ şi $i{~2~}$ astfel încât $j < i{~1~} < i{~2~} &le; i$. Atunci, dacă $S[i{~2~}] > S[i{~1~}]$ poziţia $i{~2~}$ va fi întotdeauna preferată poziţiei $i{~1~}$ atâta timp cât cele două poziţii vor fi în intervalul $(j, i]$. Când $i{~1~}$ şi $i{~2~}$ nu vor mai fi ambele în intervalul $(j, i]$, poziţia eliminată va fi $i{~1~}$. Dacă însă $S[i{~1~}] > S[i{~2~}]$, atunci poziţia $i{~1~}$ va umbri poziţia $i{~2~}$ atâta timp cât cele două poziţii vor fi în intervalul $(j, i]$. Când $i{~1~}$ va fi eliminat, atunci e posibil ca $i{~2~}$ să fie un candidat la $MAX$ dintre restul elementelor de la dreapta sa. În acest caz, nu putem afirma nimic şi vom păstra cele două poziţii.
Rezultă din această observaţie, analog 'problemei anterioare':deque-si-aplicatii#problema-2,  în intervalul $[j, i]$ se va forma un şir de poziţii $i{~1~} < i{~2~} < ... < i{~k~}$ astfel încât $S[i{~1~}] &ge; S[i{~2~}] &ge; ... &ge; S[i{~k~}]$, din care extragem $MAX$ ca fiind $S[i{~1~}]$. Folosind iarăşi structura de date $deque$, complexitatea algoritmului va fi $O(N)$.
Rezultă din această observaţie, precum în 'problema anterioară':deque-si-aplicatii#problema-2, că în intervalul $(j, i]$ se va forma un şir de poziţii $i{~1~} < i{~2~} < .. < i{~k~}$ astfel încât $S[i{~1~}] > S[i{~2~}] > .. > S[i{~k~}]$, din care obţinem că $MAX$ este egal cu $S[i{~1~}]$. Când îl vom incrementa pe $i$ la $i + 1$ vom şterge din poziţiile $i{~k~}$, $i{~k-1~}$, ... atâta timp cât $S[i + 1]$ este mai important, adică mai mare decât valorile de pe aceste poziţii, şi vom şterge $i{~1~}$, $i{~2~}$, ... atâta timp cât aceste poziţii sunt mai mici sau egale decât $j'$. Indicele $j'$ este noul optim pentru poziţia $i + 1$. Proprietatea şirului de poziţii $i{~1~}, i{~2~}, .., i{~k~}$ este că se reprezintă ca un şir continuu de numere care permite inserarea elementelor prin dreapta şi ştergerea prin stânga, adică se adaugă elemente la tail şi se şterg elemente de la head. Îl putem deci reprezenta printr-un deque. Complexitatea $O(1)$ amortizat provine de la faptul că fiecare poziţie dintre cele $N$ nu trece decât o singură dată prin deque şi este şters tot cel mult o singură dată.
 
În practică, pseudocodul poate arăta în felul următor:
În pseudocod, algoritmul va arăta în felul următor:
== code(cpp) |
// S şirul de numere iniţial şi N lungimea sa
Subalgoritmul push_in(deque, întreg p, funcţia fct) este:
// Subalgoritmul push() inserează în deque poziţia p din şirul S în conformitate cu
// funcţia booleană fct, o funcţie generică
Subalgoritmul push(deque, întreg p, funcţia fct) este:
    cât timp (!deque.empty() şi fct(S[p], S[deque.back()])) execută
        deque.pop_back();
    deque.push_back(p);
Sfârşit;
// Funcţia query() întoarce numărul din S corespunzător primului indice
// din deque aflat în intervalul de interes [j, i].
Funcţia query(deque, întreg j) este:
    cât timp (!deque.empty() şi deque.front() <= j) execută
    cât timp (!deque.empty() şi deque.front() < j) execută
        deque.pop_front();
    return S[deque.front()];
Sfârşit;
Algoritmul este:
    lg = 0;
    lg = 0; j = 1;
    pentru i = 1, N execută
        // funcţia min(a, b) întoarce true dacă a < b
        inserează(min_deq, i, min);
        push(min_deq, i, min);
        // funcţia max(a, b) întoarce true dacă a > b
        inserează(max_deq, i, max);
        cât timp ((j < i - Y sau query(max_deq, j) - query(min_deq, j) > Z) şi j < i - X) execută
        push(max_deq, i, max);
        cât timp ((j <= i - Y sau query(max_deq, j) - query(min_deq, j) > Z) şi j <= i - X + 1) execută
            j = j + 1;
        // (j, i] este intervalul candidat la soluţia optimă pentru poziţia i
        dacă (j <= i - X) şi (query(max_deq, j) - query(min_deq, j) <= Z) atunci
            dacă (lg >= i - j) atunci
                lg = i - j, start = j + 1, stop = i;
        // [j, i] este intervalul candidat la soluţia optimă pentru poziţia i
        dacă (j <= i - X + 1) şi (query(max_deq, j) - query(min_deq, j) <= Z) atunci
            dacă (lg <= i - j + 1) atunci
                lg = i - j + 1, start = j, stop = i;
    sfârşit_pentru
    dacă (lg > 0) atunci
        scrie lg, start, stop;
        soluţia este (lg, start, stop);
    altfel
        scrie -1;
        nu există soluţie;
Sfârşit.
==
Complexitatea finală va fi $O(N)$.
 
h2(#problema-4). 4. 'Platforma':http://campion.edu.ro/problems/3/509/platforma_ro.htm (.campion, 2009)
h2(#problema-4). 4. 'Platforma':http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=85 (.campion, 2009)
bq. Se dă o matrice $P$ de dimensiuni $M x N$ cu elemente numere întregi. Se defineşte valoarea maximă dintr-un dreptunghi de dimensiuni $R x C$ ca fiind valoarea maximă dintre elementele aflate în acel dreptunghi.
Cerinţă: Să se găsească un dreptunghi de dimensiuni $R x C$ cu valoarea maximă minimă.
Această problemă reprezintă o extindere în două dimensiuni a problemei anterioare 'Vila 2':deque-si-aplicatii#problema-2, unde am studiat cazul unidimensional al determinării pe un vector a maximului / minimului pentru fiecare subsecvenţă de o lungime fixată.
Cerinţa constă în amplasarea unui dreptunghi $R x C$ astfel încât valoarea maximă din interiorul său să fie cât mai mică. Una din ideile simple constă în fixarea colţului din stânga sus în toate cele $(M - R) x (N - C)$ poziţii şi determinarea maximului din interiorul său cu o altă parcurgere a celor $R x C$ elemente. Dar, să fixăm o linie $i$. Atunci, pentru a fixa colţul din stânga sus mai iterăm cu un indice $j$ între coloanele $1$ şi $N-C+1$. De aici devine clar că atunci când avansăm indicele coloanei în dreptunghiul curent apare o nouă coloană, $j + C$, şi dispare coloana curentă $j$. Dacă pentru fiecare coloană $j$ de pe linia curentă $i$ reţinem un $Max{~i,j~}$ egal cu maximul dintre elementele $P{~i,j~}, P{~i+1,j~},.. P{~i+R-1,j~}$, atunci pe linia fixată $i$ vom avea un vector din $N$ elemente (numărul de coloane al matricei $P$) alcătuit din valorile $Max{~i,1~}, Max{~i,2~}, Max{~i,3~},.. Max{~i,j~},.. Max{~i,N-1~}, Max{~i,N~}$. Iar pe acest vector va trebui să determinăm pentru fiecare subsecvenţă de $C$ elemente, valoarea maximă. Dintre toate subsecvenţele o vom alege pe cea cu valoarea maximă cea mai mică. Iar acest rezultat va fi o soluţie pentru linia fixată. Cu valorile din $Max$ precalculate, pentru fiecare linie avem complexitatea $O(N)$, deci $O(M * N)$ pentru întreaga matrice. Însă, implementând direct, valorle din $Max$ se calculează în $O(M * N * R)$. Mai sus am definit $Max{~i,j~}$ ca fiind maximul dintre $P{~i,j~}, P{~i+1,j~},.. P{~i+R-1,j~}$. Rezultă că $Max{~i+1,j~}$ este maximul dintre $P{~i+1,j~}, P{~i+2,j~},.. P{~i+R-1,j~}, P{~i+R,j~}$, adică maximul dintre elementele lui $Max{~i,j~}$ din care scoatem $P{~i,j~}$ şi adăugăm $P{~i+R,j~}$. De aici deducem că pentru fiecare coloană fixată, valorile lui $Max$ de pe coloana respectivă se reduc la a determina pentru fiecare subsecvenţă de lungime $R$ (numărul de linii al dreptunghiului de amplasat) elementul maxim. Aceste rezultate se obţin în $O(M)$ pentru fiecare coloană, deci $O(N * M)$ în total.
Cerinţa constă în amplasarea unui dreptunghi $R x C$ astfel încât valoarea maximă din interiorul său să fie cât mai mică. Una din ideile simple constă în fixarea colţului din stânga sus în toate cele $(M - R + 1) x (N - C + 1)$ poziţii şi determinarea maximului din interiorul său cu o altă parcurgere a celor $R x C$ elemente. Putem, în schimb, să fixăm o linie $i$, iar pentru a fixa colţul din stânga sus mai iterăm cu un indice $j$ între coloanele $1$ şi $N - C + 1$. De aici devine clar că atunci când avansăm indicele coloanei, în dreptunghiul curent apare o nouă coloană, $j + C$, şi dispare coloana $j$. Dacă pentru fiecare coloană $j$ de pe linia curentă $i$ reţinem un $Max{~i,j~}$ egal cu maximul dintre elementele $P{~i,j~}, P{~i+1,j~}, ..., P{~i+R-1,j~}$, atunci pe linia fixată $i$ vom avea un vector din $N$ elemente (numărul de coloane al matricei $P$) alcătuit din valorile $Max{~i,1~}, Max{~i,2~}, Max{~i,3~}, ..., Max{~i,j~}, ..., Max{~i,N-1~}, Max{~i,N~}$. Iar pe acest vector va trebui să determinăm pentru fiecare subsecvenţă de $C$ elemente, valoarea maximă. Dintre toate subsecvenţele o vom alege pe cea cu valoarea maximă cea mai mică. Iar acest rezultat va fi o soluţie pentru linia fixată. Cu valorile din $Max$ precalculate, pentru fiecare linie avem complexitatea $O(N)$, deci $O(M * N)$ pentru întreaga matrice. Însă, implementând direct, valorile din $Max$ se calculează în $O(M * N * R)$. Mai sus am definit $Max{~i,j~}$ ca fiind maximul dintre $P{~i,j~}, P{~i+1,j~}, ..., P{~i+R-1,j~}$. Rezultă că $Max{~i+1,j~}$ este maximul dintre $P{~i+1,j~}, P{~i+2,j~}, ..., P{~i+R-1,j~}, P{~i+R,j~}$, adică maximul dintre elementele lui $Max{~i,j~}$ din care scoatem $P{~i,j~}$ şi adăugăm $P{~i+R,j~}$. De aici deducem că pentru fiecare coloană fixată, valorile lui $Max$ de pe coloana respectivă se reduc la a determina pentru fiecare subsecvenţă de lungime $R$ (numărul de linii al dreptunghiului de amplasat) elementul maxim. Aceste rezultate se obţin în $O(M)$ pentru fiecare coloană, deci $O(N * M)$ în total.
Rezultă complexitatea finală $O(M * N)$.
h2(#problema-5). 5. 'Trans':problema/trans (ONI 2004)
bq. Se dau $N$ blocuri de piatră, de culoare albă sau neagră aşezate în ordinea $1$, $2$,.., $N$. Blocurile de piatră trebuie să fie transportate în ordinea în care sunt, iar pentru aceasta va trebui închiriat un camion. Se mai dau $Q$ tipuri de camioane. Camionul de tipul $i (1 &le; i &le; Q)$ poate transporta maxim $K{~i~}$ blocuri de piatră la un moment dat şi pentru un transport se percepe taxa $T{~i~}$. Se impune condiţia ca toate blocurile de piatră plasate în camion la un transport sa aibă aceeaşi culoare. Aşadar, pentru a fi transportate toate blocurile, se va alege un camion de un anumit tip, iar camionul va efectua unul sau mai multe transporturi. Pentru a micşora suma totală plătită, există posibilitatea de a schimba culoarea oricărui bloc de piatră (din alb în negru sau din negru în alb); pentru fiecare bloc $i (1 &le; i &le; N)$ se cunoaşte suma $S{~i~}$ ce trebuie plătită pentru a-i schimba culoarea $C{~i~}$.
bq. Se dau $N$ blocuri de piatră, de culoare albă sau neagră aşezate în ordinea $1$, $2$, ..., $N$. Blocurile de piatră trebuie să fie transportate în ordinea în care sunt, iar pentru aceasta va trebui închiriat un camion. Se mai dau $Q$ tipuri de camioane. Camionul de tipul $i (1 &le; i &le; Q)$ poate transporta maxim $K{~i~}$ blocuri de piatră la un moment dat şi pentru un transport se percepe taxa $T{~i~}$. Se impune condiţia ca toate blocurile de piatră plasate în camion la un transport sa aibă aceeaşi culoare. Aşadar, pentru a fi transportate toate blocurile, se va alege un camion de un anumit tip, iar camionul va efectua unul sau mai multe transporturi. Pentru a micşora suma totală plătită, există posibilitatea de a schimba culoarea oricărui bloc de piatră (din alb în negru sau din negru în alb); pentru fiecare bloc $i (1 &le; i &le; N)$ se cunoaşte suma $S{~i~}$ ce trebuie plătită pentru a-i schimba culoarea $C{~i~}$.
Cerinţă: Pentru fiecare dintre cele $Q$ tipuri de camioane, determinaţi suma minimă plătită pentru a transporta toate cele $N$ blocuri.
Restricţii: $1 &le; N &le; 16 000$, $1 &le; Q &le; 100$, $1 &le; K{~i~} &le; N$.
Restricţii: $1 &le; N &le; 16.000$, $1 &le; Q &le; 100$, $1 &le; K{~i~} &le; N$.
h3. Soluţie:
Soluţia problemei se bazează pe găsirea unei formule de recurenţă ce respectă principiul optimalităţii al metodei programării dinamice.
Soluţia problemei se bazează pe găsirea unei formule de recurenţă ce respectă principiul optimalităţii specific metodei programării dinamice.
Pentru început, fixăm un camion dintre cele <tex> Q </tex>. Fie <tex> K </tex> numărul maxim de pietre pe care acesta le poate transporta şi <tex> T </tex> taxa percepută. Notăm <tex> sum_{i,c} </tex> costul pentru a schimba toate pietrele <tex> 1, 2, \ldots, i </tex> în culoarea <tex> c </tex> (<tex> c = 0 </tex> pentru alb şi <tex> c = 1 </tex> pentru negru). Rezultă că în <tex> sum_{i,c} </tex> se vor însuma toate valorile <tex> S_{j} </tex>, cu <tex> j \le i </tex> pentru care <tex> C_{j} = 1 - c </tex>.
În continuare, considerăm <tex> bst_{i,c} </tex> costul minim pentru a transporta pietrele <tex> 1, 2, \ldots, i </tex>, iar ultimul transport conţine pietre de culoare <tex> c </tex>. Întrucât nu putem transporta mai mult de <tex> K </tex> pietre, <tex> bst_{i,c} </tex> depinde doar de poziţiile <tex> i - K, i - K + 1, \ldots, i - 1 </tex>. Cunoaştem că ultimul camion va transporta o secvenţă continuă de pietre începând de la o poziţie <tex> j + 1 </tex> până la poziţia <tex> i </tex>, unde <tex> i - K \le j \le i - 1 </tex>. Astfel, pentru  fiecare <tex> j </tex> în intervalul precedent, costul va fi <tex> Min(bst_{j,0}, bst_{j,1}) </tex> (transportăm primele <tex> j </tex> pietre cât mai ieftin) adunat cu <tex> sum_{i,c} - sum_{j,c} </tex> (costul transformării pietrelor <tex> j + 1, \ldots, i </tex> în culoarea <tex> c </tex>) şi plus taxa <tex> T </tex>. Rezultă recurenţa:
În continuare, considerăm <tex> bst_{i,c} </tex> costul minim pentru a transporta pietrele <tex> 1, 2, \ldots, i </tex>, iar ultimul transport conţine pietre de culoare <tex> c </tex>. Întrucât nu putem transporta mai mult de <tex> K </tex> pietre, <tex> bst_{i,c} </tex> depinde doar de poziţiile <tex> i - K, i - K + 1, \ldots, i - 1 </tex>. Cunoaştem că ultimul camion va transporta o secvenţă continuă de pietre începând de la o poziţie <tex> j + 1 </tex> până la poziţia <tex> i </tex>, unde <tex> i - K \le j \le i - 1 </tex>. Astfel, pentru fiecare <tex> j </tex> în intervalul precedent, costul va fi <tex> Min(bst_{j,0}, bst_{j,1}) </tex> (transportăm primele <tex> j </tex> pietre cât mai ieftin) adunat cu <tex> sum_{i,c} - sum_{j,c} </tex> (costul transformării pietrelor <tex> j + 1, \ldots, i </tex> în culoarea <tex> c </tex>) şi plus taxa <tex> T </tex>. Rezultă recurenţa:
* <tex> bst_{i,c} = Min\ \{\ Minim(bst_{j,0},\ bst_{j,1}) + sum_{i,c} - sum_{j,c} + T\ :\ i - K \le j \le i - 1\ \}; </tex>
* <tex> bst_{i,c} = Min\ \{\ Minim(bst_{j,0},\ bst_{j,1}) - sum_{j,c}\ :\ i - K \le j \le i - 1\ \} + sum_{i,c} + T; </tex>
Notez în continuare, pentru uşurinţă în scriere, <tex> T_{j,c} = Min(bst_{j,0}, bst_{j,1}) - sum_{j,c} </tex>. Să fixăm doi indici <tex> i_{1} </tex> şi <tex> i_{2} </tex>, astfel încât <tex> i - K \le i_{1} < i_{2} \le i - 1 </tex>. Dacă <tex> T_{i_{1},c} > T_{i_{2},c} </tex> atunci întotdeauna poziţia <tex> i_{2} </tex> va fi preferată poziţiei <tex> i_{1} </tex>. Când cele două nu se vor mai afla ambele în intervalul <tex> [i - K, i - 1] </tex>, poziţia eliminată va fi poziţia <tex> i_{1} </tex>. Dacă <tex> T_{i_{1},c} < T_{i_{2},c} </tex>, atunci nu putem decide care poziţie este mai bună în viitor, aşa că le vom păstra pe ambele. Rezultă mai departe că în intervalul <tex> [i - K, i - 1] </tex> vom avea o serie de indecşi candidaţi la minim <tex> i - K \le i_{1} < i_{2} < \ldots < i_{n} \le i - 1 </tex> astfel încât <tex> T_{i_{1},c} < T_{i_{2},c} <  .. < T_{i_{n},c} </tex>. Mai departe, găsim <tex> bst_{i,c} = T_{i_{1},c} + sum_{i,c} + T </tex>. Urmează să îl introducem şi pe <tex> T_{i,c} </tex> în şirul de indecşi de mai sus, el fiind egal cu <tex> Minim(bst_{i,0}, bst_{i,1}) - sum_{i,c} </tex>. Acest lucru se va face în felul următor: se vor elimina din <tex> i_{n}, , i_{n-1}, \ldots </tex> atâta timp cât <tex> T_{i_{n},c} > T_{i,c} </tex>, <tex> T_{i_{n-1},c} > T_{i,c} \ldots </tex> adică atâta timp cât poziţia <tex> i </tex> este preferată lui <tex> i_{n}, i_{n-1}, \ldots </tex>. Fiind la poziţia <tex> i + 1 </tex>, intervalul se va transforma în <tex> [i - K + 1, i] </tex>, aşadar, vom mai elimina din primii indici <tex> i_{1}, i_{2}, \ldots </tex> atâta timp cât <tex> i_{1} < i - K + 1, i_{2} < i - K + 1, \ldots </tex>.
Notez în continuare, pentru uşurinţă în scriere, <tex> T_{j,c} = Min(bst_{j,0}, bst_{j,1}) - sum_{j,c} </tex>. Să fixăm doi indici <tex> i_{1} </tex> şi <tex> i_{2} </tex>, astfel încât <tex> i - K \le i_{1} < i_{2} \le i - 1 </tex>. Dacă <tex> T_{i_{1},c} > T_{i_{2},c} </tex> atunci întotdeauna poziţia <tex> i_{2} </tex> va fi preferată poziţiei <tex> i_{1} </tex>. Când cele două nu se vor mai afla ambele în intervalul <tex> [i - K, i - 1] </tex>, poziţia eliminată va fi poziţia <tex> i_{1} </tex>. Dacă <tex> T_{i_{1},c} \le T_{i_{2},c} </tex>, atunci nu putem decide care poziţie este mai bună în viitor, aşa că le vom păstra pe ambele. Rezultă mai departe, după cum am arătat în problemele anterioare, că în intervalul <tex> [i - K, i - 1] </tex> vom avea o serie de indecşi candidaţi la minim <tex> i - K \le i_{1} < i_{2} < \ldots < i_{n} \le i - 1 </tex> astfel încât <tex> T_{i_{1},c} \le T_{i_{2},c} \le  ... \le T_{i_{n},c} </tex>. Mai departe, găsim <tex> bst_{i,c} = T_{i_{1},c} + sum_{i,c} + T </tex>. Urmează să îl introducem şi pe <tex> T_{i,c} </tex> în şirul de indecşi de mai sus, el fiind egal cu <tex> Minim(bst_{i,0}, bst_{i,1}) - sum_{i,c} </tex>. Acest lucru se va face în felul următor: se vor elimina din <tex> i_{n}, , i_{n-1}, \ldots </tex> atâta timp cât <tex> T_{i_{n},c} > T_{i,c} </tex>, <tex> T_{i_{n-1},c} > T_{i,c} \ldots </tex> adică atâta timp cât poziţia <tex> i </tex> este preferată lui <tex> i_{n}, i_{n-1}, \ldots </tex>. Fiind la poziţia <tex> i + 1 </tex>, intervalul se va transforma în <tex> [i - K + 1, i] </tex>, aşadar, vom mai elimina din primii indici <tex> i_{1}, i_{2}, \ldots </tex> atâta timp cât <tex> i_{1} < i - K + 1, i_{2} < i - K + 1, \ldots </tex>.
După cum am arătat şi la problema precedentă, acest şir de indecşi <tex> i_{1}, i_{2}, \ldots, i_{n} </tex> are proprietatea că este un şir continuu de numere care admite inserări prin dreapta (tail) şi ştergeri prin stânga (head). Şir ce poate fi reprezentat printr-un deque. Cum fiecare index dintre <tex> 1, 2, \ldots, N </tex> va trece o singură dată prin deque, complexitatea soluţiei va fi <tex> O(N) </tex> pentru fiecare camion, deci <tex> O(Q * N) </tex> în total.
După cum am arătat şi la problema precedentă, acest şir de indecşi <tex> i_{1}, i_{2}, \ldots, i_{n} </tex> are proprietatea că este un şir continuu de numere care admite inserări şi ştergeri pe la capete ({$head$} şi {$tail$}), şir ce poate fi reprezentat printr-un deque. Cum fiecare index dintre <tex> 1, 2, \ldots, N </tex> va fi adăugat şi şters cel mult o singură dată din deque, complexitatea soluţiei va fi <tex> O(N) </tex> pentru fiecare camion, deci <tex> O(Q * N) </tex> în total.
În practică, programul este scurt, clar şi eficient:
Iată şi o sursă scurtă, clară şi eficientă pentru această problemă:
== code(cpp) |
#include <iostream>
#define MAXN  16005
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define FOR(i, a, b)  for (int i = (a); i <= (b); ++ i)
#define FOR(i, a, b)  for (int i = (a); i <= (b); ++i)
int C[MAXN], S[MAXN], bst[MAXN][2], sum[MAXN][2], N;
    return Min(bst[N][0], bst[N][1]);
}
int main(void)
{
int main(void) {
    ifstream in(iname);  ofstream out(oname);
    in >> N;
    FOR (i, 1, N) {
h2(#problema-6). 6. 'Otilia':problema/otilia  (.campion, 2005)
bq. Otilia şi Burbucel au o grămadă de $N$ pietre şi vor juca un joc cu următoarele trei reguli: 1. Primul jucător are voie să ia din gramadă cel mult $K$ piese; 2. Cu excepţia primei mutări, fiecare jucător are voie să ia maxim $P * t$ pietre, unde $t$ este numărul de pietre care au fost substituite din grămadă la mutarea precedentă; 3. Pierde cel care mută ultimul (cel care ia ultimele pietre din grămadă).
Cerinţă: Se dau $M$ jocuri prin numerele $N$, $K$ şi $P$. Se cere să se determină dacă Otilia va câştiga fiecare din jocuri sau nu.
Restricţii: $1 &le; M &le; 30 000$, $1 &le; N &le; 5 000 000$, $1 &le; K &le; N$, $1 &le; P &le; 10$.
Cerinţă: Se dau $M$ jocuri prin numerele $N$, $K$ şi $P$. Se cere să se determine pentru fiecare joc dacă Otilia va câştiga sau nu.
Restricţii: $1 &le; M &le; 30.000$, $1 &le; N &le; 5.000.000$, $1 &le; K &le; N$, $1 &le; P &le; 10$.
h3. Soluţie (Silviu Ganceanu):
h3. Soluţie (Silviu Gănceanu):
Problema se rezolvă prin programare dinamică. Soluţia se bazează pe observaţia de mai jos. Considerăm $P$-ul fixat şi notăm cu $stare(X, Y)$ poziţia de start în care avem $X$ pietre şi numărul maxim de pietre care se pot lua la prima mutare este $Y$.
bq. Se consideră $N$ camere, numerotate de la $1$ la $N$, aşezate în cerc. Iniţial (la momentul de timp 0), ne aflăm în camera $1$. În fiecare moment de timp, putem alege să rămânem în camera în care ne aflăm sau să ne deplasăm într-o cameră vecină într-o unitate de timp. Se dă o listă de $M$ cutii ce conţin bomboane prin $T$, $C$ şi $B$: cutia apare la momentul $T$ în camera $C$ şi conţine $B$ bomboane. Cutia va dispărea la momentul $T + 1$.
Cerinţă: Cunoscând numărul de camere din labirint şi momentele de timp la care apar cutiile cu bomboane, determinaţi care este numărul maxim de bomboane pe care le putem culege.
Restricţii: $3 &le; N &le; 2 048$, $0 &le; M &le; 50 000$, $1 &le; T &le; 1 000 000 000$, $1 &le; C &le; N$, $1 &le; B &le; 9 999$.
Restricţii: $3 &le; N &le; 2.048$, $0 &le; M &le; 50.000$, $1 &le; T &le; 1.000.000.000$, $1 &le; C &le; N$, $1 &le; B &le; 9.999$.
h3. Soluţie:
Soluţia foloseşte metoda programării dinamice.
O stare se reprezintă prin camera în care ne aflăm şi momentul de timp. Fie <tex> bst_{i,j} </tex> numărul maxim de bomboane culese până în momentul <tex> i </tex> când ne găsim în camera <tex> j </tex>. O observaţie evidentă este că <tex> bst_{i,j} </tex> se poate modifica doar în momentele în care apar cutiile. Prin urmare, vom considera momentele de timp când apar cutiile, momente ce sunt în număr de <tex> M </tex>, <tex> bst_{i,j} </tex> însemnând numărul maxim de bomboane culese ştiind că ne aflăm în camera <tex> j </tex> unde am cules cutia <tex> i </tex>. De cine depinde această stare? Ştim că <tex> bst_{i-1,1 \ldots N} </tex> a fost deja calculat în mod optim. Să notăm cu <tex> T </tex> diferenţa de timp dintre momentele la care apare cutia <tex> i </tex> şi cutia <tex> i - 1 </tex>. În această stare, <tex> i </tex> şi cameră <tex> j </tex>, putem ajunge din maxim <tex> T </tex> camere spre stânga sau spre dreapta, întrucât fiecare deplasare între două camere costă o unitate de timp. De unde deducem că:
O stare se reprezintă prin camera în care ne aflăm şi momentul de timp. Fie <tex> bst_{i,j} </tex> numărul maxim de bomboane culese până în momentul <tex> i </tex> când ne găsim în camera <tex> j </tex>. O observaţie evidentă este că <tex> bst_{i,j} </tex> se poate modifica doar în momentele în care apar cutiile. Prin urmare, vom considera momentele de timp când apar cutiile, momente ce sunt în număr de <tex> M </tex>, <tex> bst_{i,j} </tex> însemnând numărul maxim de bomboane culese ştiind că ne aflăm în camera <tex> j </tex> după ce am cules cutia <tex> i </tex>. De cine depinde această stare? Ştim că <tex> bst_{i-1,1 \ldots N} </tex> a fost deja calculat în mod optim. Să notăm cu <tex> T </tex> diferenţa de timp dintre momentele la care apar cutia <tex> i </tex> şi cutia <tex> i - 1 </tex>. În această stare, cutie <tex> i </tex> şi cameră <tex> j </tex>, putem ajunge din maxim <tex> T </tex> camere spre stânga sau spre dreapta, întrucât fiecare deplasare între două camere costă o unitate de timp. De unde deducem că:
* <tex> bst_{i,j} = Min\{\ bst_{i-1,j-T},\ bst_{i-1,j-T+1}, \ldots,\ bst_{i-1,j}, \ldots,\ bst_{i-1,j+T-1},\ bst_{i-1,j+T}\ \}; </tex>
* <tex> bst_{i,j} = Max\{\ bst_{i-1,j-T},\ bst_{i-1,j-T+1}, \ldots,\ bst_{i-1,j}, \ldots,\ bst_{i-1,j+T-1},\ bst_{i-1,j+T}\ \}; </tex>
Metoda directă, şi aparent eficientă, constă în folosirea unui arbore de intervale pentru aflarea acestui minim. Însă, intervalul <tex> [j-T,j+T] </tex> se deplasează constant spre dreapta, dacă vom considera indicii <tex> j </tex> în ordine <tex> 1, 2, 3, \ldots </tex>. În acest interval noile elemente se introduc prin dreapta şi altele se elimină prin stânga. Însă, cum am arătat în problemele precedente, nu avem nevoie de toate valorile din acest interval. Şi din acest motiv vom folosi un deque de lungime <tex> T * 2 + 1 </tex> cu care vom elimina poziţiile care nu sunt candidate la soluţie. Mai jos este o reprezentare grafică a acestei explicaţii.
Metoda directă, şi aparent eficientă, constă în folosirea unui arbore de intervale pentru aflarea acestui maxim. Însă, intervalul <tex> [j-T,j+T] </tex> se deplasează constant spre dreapta, dacă vom considera indicii <tex> j </tex> în ordine <tex> 1, 2, 3, \ldots </tex>. În acest interval noile elemente se introduc prin dreapta şi altele se elimină prin stânga. Însă, cum am arătat în problemele precedente, nu avem nevoie de toate valorile din acest interval. Şi din acest motiv vom folosi un deque de lungime maximă <tex> T * 2 + 1 </tex> cu care vom elimina poziţiile care nu sunt candidate la soluţie. Mai jos este o reprezentare grafică a deplasării intervalului menţionat mai sus.
p=. !deque-si-aplicatii?bcrc.png 40%!
h2(#problema-8). 8. 'Cut the Sequence':http://acm.pku.edu.cn/JudgeOnline/problem?id=3017 (PKU)
bq. Se dă o secvenţă $S$ de numere întregi de lungime $N$. Va trebui să se împartă secvenţa în mai multe subsecvenţe astfel încât suma valorilor din fiecare parte să nu depăşească un număr întreg $M$ dat, iar dacă însumăm maximul din fiecare subsecvenţă să obţinem o sumă cât mai mică.
Restricţii: $0 &lt; N &le; 100 000$, $0 &le; S{~i~} &le; 1 000 000$.
bq. Se dă o secvenţă $S$ de $N$ numere întregi. Va trebui să se împartă secvenţa în mai multe subsecvenţe astfel încât suma valorilor din fiecare parte să nu depăşească un număr întreg $M$ dat, iar dacă însumăm maximul din fiecare subsecvenţă să obţinem o sumă cât mai mică.
Restricţii: $0 &lt; N &le; 100.000$, $0 &le; S{~i~} &le; 1.000.000$.
h3. Soluţie:
Implementarea directă a acestei recurenţe conduce la un algoritm de complexitate <tex> O(N^{2}) </tex>, dar care pentru restricţiile impuse nu este de ajuns.
Să obţinem în continuare alte informaţii. Fie indicele <tex> j </tex> minim astfel încât <tex> \displaystyle\sum_{k=j+1}^{i} \le M </tex>. Maximul obţinut din mulţimea <tex> \{S_{j+1},.., S_{i}\} </tex> se găseşte pe o poziţie <tex> j^{'} </tex> unde <tex> j < j^{'} \le i </tex>. Însă, orice indice <tex> k </tex> cu <tex> j \le k < j^{'} </tex> are proprietatea că rezultatul expresiei <tex> Max\{S_{k+1},.., S_{i}\} </tex> se găseşte pe poziţia <tex> j^{'} </tex>. Rezultă că <tex> \forall k \in \{j, j+1,.., j^{'}-1\} </tex>, <tex> bst_{i} </tex> poate fi îmbunătăţit cu valoarea <tex> bst_{k} + S_{j^{'}} </tex>. Minimul mulţimii <tex> \{bst_{k} + S_{j^{'}} : \forall k \in \{j, j+1,.., j^{'}-1\}\} </tex> este egal cu minimul expresiei <tex> \{bst_{k} : \forall k \in \{j, j+1,.., j^{'}-1\}\} + S_{j^{'}} (*) </tex>, deci, schimbând reperele, pentru maximul de pe poziţia <tex> j^{'} </tex>, dacă lungimea secvenţei care se termină în <tex> i </tex> este cel puţin <tex> i-j^{'}+1 </tex>, atunci optimul se obţine calculând rezultatul expresiei <tex> (*) </tex>. Pentru minimul pe un interval, <tex> [j, j^{'}-1] </tex> al valorile vectorului <tex> bst </tex>, putem folosi un arbore de intervale pentru <tex> O(log_{2}N) </tex> pe interogare.
Să obţinem în continuare alte informaţii. Fie indicele <tex> j </tex> minim astfel încât <tex> \displaystyle\sum_{k=j+1}^{i} \le M </tex>. Maximul obţinut din mulţimea <tex> \{S_{j+1},.., S_{i}\} </tex> se găseşte pe o poziţie <tex> j^{'} </tex> unde <tex> j < j^{'} \le i </tex>. Însă, orice indice <tex> k </tex> cu <tex> j \le k < j^{'} </tex> are proprietatea că rezultatul expresiei <tex> Max\{S_{k+1},.., S_{i}\} </tex> se găseşte pe poziţia <tex> j^{'} </tex>. Rezultă că <tex> \forall k \in \{j, j+1,.., j^{'}-1\} </tex>, <tex> bst_{i} </tex> poate fi îmbunătăţit cu valoarea <tex> bst_{k} + S_{j^{'}} </tex>. Minimul mulţimii <tex> \{bst_{k} + S_{j^{'}} : \forall k \in \{j, j+1,.., j^{'}-1\}\} </tex> este egal cu minimul expresiei <tex> \{bst_{k} : \forall k \in \{j, j+1,.., j^{'}-1\}\} + S_{j^{'}} (*) </tex>, deci, schimbând reperele, pentru maximul de pe poziţia <tex> j^{'} </tex>, dacă lungimea secvenţei care se termină în <tex> i </tex> este cel puţin <tex> i-j^{'}+1 </tex>, atunci optimul se obţine calculând rezultatul expresiei <tex> (*) </tex>. Pentru minimul valorilor vectorului <tex> bst </tex> pe un interval <tex> [j, j^{'}-1] </tex> putem folosi un arbore de intervale pentru <tex> O(log_{2}N) </tex> pe interogare.
Dar, lungimea optimă a ultimei secvenţe ce se termină în <tex> i </tex> poate fi mai mică decât <tex> i-j^{'}+1 </tex>, deci poate fi cel mult <tex> i-j^{'} </tex>. Optimul se găseşte printre elementele mulţimii <tex> \{bst_{k} + Max\{S_{k+1},..,S_{i}\} : j^{'} \le k < i\} </tex>. Dacă procedăm ca la pasul anterior vom obţine un alt indice <tex> j^{''} </tex> cu aceleaşi proprietăţi pentru secvenţa <tex> [j^{'}, i] </tex> precum <tex> j^{'} </tex> pentru secvenţa <tex> [j, i] </tex>.
Cu ajutorul relaţiei <tex> (*) </tex> şi a şirului <tex> j_{1} < j_{2} < .. < j_{K} = i </tex> vom construi un alt vector <tex> iMin </tex> cu proprietatea că <tex> iMin_{p} = Min\{bst_{r} + S_{j_{p}} : j_{p-1} \le r < j_{p}\} </tex>. În final, <tex> bst_{i} = Minim\{iMin_{1}, iMin_{2}, .., iMin_{K}\} </tex>, rezultat pe care îl putem obţine în <tex> O(log_{2}N) </tex> dacă folosim un arbore de intervale.
Însă, cum se construieşte şirul <tex> j_{1} < j_{2} < .. < j_{K} = i </tex>? În 'a doua problemă':deque-si-aplicatii#problema-2 am construit cu ajutorul unui deque exact şirul de indici de care avem nevoie aici. Când vom înainta la indicele <tex> i + 1 </tex> vom modifica şirul astfel încât să respecte proprietăţile de mai sus utilizând operaţiile normale asupra unui deque. Mai sus am menţionat cum se obţine <tex> bst_{i} </tex> lucru care implică combinarea structurilor de deque şi arbore de intervale. Arborele de intervale reţine valorile lui <tex> iMin </tex> pentru fiecare element al dequelui.
Însă, cum se construieşte şirul <tex> j_{1} < j_{2} < .. < j_{K} = i </tex>? În 'a doua problemă':deque-si-aplicatii#problema-2 am construit cu ajutorul unui deque exact şirul de indici de care avem nevoie aici. Când vom înainta la indicele <tex> i + 1 </tex> vom modifica şirul astfel încât să respecte proprietăţile de mai sus utilizând operaţiile normale asupra unui deque. Mai sus am menţionat cum se obţine <tex> bst_{i} </tex> lucru care implică combinarea structurilor de deque şi arbore de intervale. Arborele de intervale reţine valorile lui <tex> iMin </tex> pentru fiecare element al deque-lui.
Pentru a înţelege cum funcţionează acest algoritm să considerăm ca date de intrare şirul <tex> S = \{5, 9, 4, 7, 4, 1, 6, 3\} </tex> şi <tex> M = 15 </tex>. Perechile din deque sunt de forma <tex> (S_{i}, iMin_{p}) </tex>. Fie <tex> i = 1, 2, \ldots 8 </tex>:
* <tex> i = 7: j = 4, head = 3, tail = 3, deque = \{\ (6, 16)\ \} \Rightarrow bst_{7} = 22; </tex>
* <tex> i = 8: j = 4, head = 3, tail = 4, deque = \{\ (6, 16),\ (3, 22)\ \} \Rightarrow bst_{8} = 22; </tex>
Mai jos se vede o figură în care elementele unui deque sunt defapt o secvenţă continuă de frunze ale unui arbore de intervale pentru cazul <tex> i = 6 </tex>.
Mai jos se vede o figură în care elementele unui deque sunt de fapt o secvenţă "continuă" de frunze ale unui arbore de intervale pentru cazul <tex> i = 6 </tex>.
p=. !deque-si-aplicatii?PKU0.png 60%!
        temp = bst[ deque[tail] ];
        cât timp (head <= tail) şi (S[ deque[tail] ] <= S[i]) execută
            temp = Min(temp, iMin[tail]);
            tail --;
            tail--;
        sfârşit;
        // adaug poziţia i la deque
        tail ++;
        tail++;
        deque[tail] = i;
        // actualizez iMin[]
        iMin[tail]  = temp;
        cât timp (sum > M) execută
            sum -= S[last];
            dacă (deque[head] == last) atunci
                head ++;
                head++;
            sfârşit;
            last ++;
            last++;
        sfârşit;
        // actualizez iMin[], Tb[] arborele de intervale pe bst[]
        iMin[head] = Query(Tb, Max(last - 1, 0), deque[head] - 1);
h2(#concluzii). Concluzii
Filozofia din spatele structurii de deque devine utilă, de obicei, în părţile finale ale rezolvării unei probleme. Însă, ce pot spune cu certitudine este că această structură de date pe cât este de simplă pe atât este de eficientă şi necesară.
Filozofia din spatele structurii de deque devine utilă, de obicei, în părţile finale ale rezolvării unei probleme. Însă, ce pot spune cu certitudine este că această structură de date, pe cât este de simplă, pe atât este de eficientă şi necesară.
h2(#probleme-suplimentare). Probleme suplimentare
Înţelegerea profundă nu se poate realiza decât prin rezolvarea a cât mai multe probleme. Succes!
Înţelegerea profundă nu se poate realiza decât prin rezolvarea a cât mai multor probleme. Succes!
* 'Deque':problema/deque, _Arhiva educaţională_
* 'Secvenţă':problema/secventa
* 'Gard':problema/gard, _ONI, 2002_
* 'Ghiozdan':problema/ghiozdan
* 'Cover':problema/cover, _Baraj ONI, 2007_
* 'Secvdist':problema/secvdist
h2(#bibliografie). Bibliografie
# D.E. Knuth - "_The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition_", Addison-Wesley, 1997
# Cosmin Negruşeri, "_Probleme cu secvenţe_":probleme-cu-secvente
# Dana Lica, "_Arbori de intervale şi aplicaţii în geometria computaţională_":arbori-de-intervale
# Cătălin Frâncu, "_Heapuri_":heapuri
# Marius Stroe, "_Treapuri_":treapuri
# wikipedia, '_Deque_':http://en.wikipedia.org/wiki/Deque
# 'C++ Reference':http://www.cplusplus.com/

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
3802