* '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

            j = j + 1;
        // [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

            dacă (lg <= i - j + 1) atunci

                lg = i - j + 1, start = j, stop = i;
    sfârşit_pentru

Sfârşit.
==

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ă.

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 ş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.

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.

Iată şi o sursă scurtă, clară şi eficientă pentru această problemă:

#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;

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 ≤ M ≤ 30 000$, $1 ≤ N ≤ 5 000 000$, $1 ≤ K ≤ N$, $1 ≤ P ≤ 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 ≤ M ≤ 30.000$, $1 ≤ N ≤ 5.000.000$, $1 ≤ K ≤ N$, $1 ≤ P ≤ 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 ≤ N ≤ 2 048$, $0 ≤ M ≤ 50 000$, $1 ≤ T ≤ 1 000 000 000$, $1 ≤ C ≤ N$, $1 ≤ B ≤ 9 999$.

Restricţii: $3 ≤ N ≤ 2.048$, $0 ≤ M ≤ 50.000$, $1 ≤ T ≤ 1.000.000.000$, $1 ≤ C ≤ N$, $1 ≤ B ≤ 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 < N ≤ 100 000$, $0 ≤ S{~i~} ≤ 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 < N ≤ 100.000$, $0 ≤ S{~i~} ≤ 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/

3802