* 'Operaţii':deque-si-aplicatii#operatii
* 'Aplicaţii':deque-si-aplicatii#aplicatii
** 'Problema 1: Book Pile (SGU)':deque-si-aplicatii#problema-1

** 'Problema 2: Şir':deque-si-aplicatii#problema-2
** 'Problema 3: Trans (ONI 2004)':deque-si-aplicatii#problema-3
** 'Problema 4: Otilia (.campion)':deque-si-aplicatii#problema-4
** 'Problema 5: Cut the Sequence (PKU)':deque-si-aplicatii#problema-5

** 'Problema 2: Vila 2':deque-si-aplicatii#problema-2
** 'Problema 3: Şir':deque-si-aplicatii#problema-3
** 'Problema 4: Trans (ONI 2004)':deque-si-aplicatii#problema-4
** 'Problema 5: Otilia (.campion)':deque-si-aplicatii#problema-5

** 'Problema 6: Bcrc (Stelele Informaticii 2006)':deque-si-aplicatii#problema-6

** 'Problema 7: Cut the Sequence (PKU)':deque-si-aplicatii#problema-7

* 'Concluzii':deque-si-aplicatii#concluzii
* 'Probleme suplimentare':deque-si-aplicatii#probleme-suplimentare
* 'Bibliografie':deque-si-aplicatii#bibliografie

Întrucât operaţiile unui deque se execută în $O(1)$ amortizat, soluţia are complexitatea $O(N + M)$.

h3(#problema-2). Problema 2: 'Şir':problema/sir

h3(#problema-2). Problema 2: 'Vila 2':problema/vila2 (.campion)
 
bq. Se dă un şir $S$ de $N$ numere întregi şi un $D$ număr natural. Se cere să determine diferenţa maximă dintre oricare două numere din şir cu proprietatea că diferenţa indicilor nu depăşeşte $D$.
Restricţii: $2 ≤ N ≤ 100 000$, $1 ≤ D ≤ N/2$.
 
h3. Soluţie:
 
Soluţia nu e greu de intuit. Considerăm indicii succesiv $1$, $2$, .. , $N$. Va trebuie ca pentru fiecare secvenţă $(i - D, i]$ să determinăm valoarea maximă şi pe cea minimă, iar diferenţa lor să o comparăm cu rezultatul obţinut până în acel moment. Pentru fixarea ideilor, să urmărim cum putem determina valoarea maximă din fiecare secvenţă $(i - D, i]$.
 
_Observaţie_: „Fie $i{~1~}$, $i{~2~}$ doi indici din astfel încât $i - D < i{~1~} < i{~2~} ≤ i$.
 
# Dacă $S[i{~1~}] < S[i{~2~}]$ atunci, cât timp cei doi indici vor fi în intervalul $(i - D, i]$, valoarea de pe poziţia $i{~2~}$ va fi întotdeauna preferată valorii de pe poziţiei $i{~1~}$. Când unul din indici nu va mai fi în acest interval, cel expediat va fi $i{~1~}$ şi, astfel, $i{~2~}$ rămâne în continuare preferat.
# Dacă $S[i{~1~}] > S[i{~2~}]$ atunci îl vom păstra pe $i{~2~}$, deoarece este candidat la maxim în viitor.”
 
Cu această observaţie deducem că într-o secvenţă $(i - D, i]$ vom avea un şir $i{~1~} < i{~2~} < ... < i{~K~}$ astfel încât $S[i{~1~}] > S[i{~2~}] > ... > S[i{~K~}]$. Când vom avansa la secvenţa următoare, $(i - D + 1, i + 1]$, vom şterge din indici $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] > S[i{~K~}]$, $S[i + 1] > S[i{~K-1~}]$... adică cât timp se îndeplineşte primul punct din observaţia anterioară.
 
Şirul $i{~1~} < i{~2~} < ... < i{~K~}$ este continuu iar operaţiile se efectuează doar pe la cele două capete. Rezultă că şirul 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:
 
p=. !deque-si-aplicatii?vila2.png 60%!
 
Cum fiecare indice din $1$, $2$, .., $N$ trece cel mult o dată prin deque complexitatea finală este $O(N)$ amortizat.
 
h3(#problema-3). Problema 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 ≤ 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 ≤ N ≤ 100 000$, $1 ≤ X ≤ Y ≤ N$, $0 ≤ Z ≤ 30 000$.

Complexitatea finală va fi $O(N)$.

h3(#problema-3). Problema 3: 'Trans':problema/trans (ONI 2004)

h3(#problema-4). Problema 4: '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 ≤ i ≤ 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 ≤ i ≤ 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.

}
==

h3(#problema-4). Problema 4: 'Otilia':problema/otilia  (.campion)

h3(#problema-5). Problema 5: 'Otilia':problema/otilia  (.campion)

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.

Este evident că prima relaţie o implică pe cea de-a doua. În momentul acesta se poate construi următorul algoritm: având lista de poziţii care pot fi bune pentru $X$ (sortată descrescător) o căutăm pe cea mai mare ca valoare care este într-adevăr bună. În principiu, scoatem din capul listei poziţiile rele până când dăm de o poziţie bună. La listă se va adăuga şi $X$ şi se va trece la pasul următor. Operaţiile algoritmului sunt chiar operaţiile asupra unui deque.

h3(#problema-5). Problema 5: 'Cut the Sequence':http://acm.pku.edu.cn/JudgeOnline/problem?id=3017 (PKU)

h3(#problema-6). Problema 6: 'Bcrc':problema/bcrc (Stelele Informaticii 2006)
 
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$.
 
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 $bst[i][j]$ numărul maxim de bomboane culese până în momentul $i$ când ne găsim în camera $j$. O observaţie evidentă este că $bst[i][j]$ 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 $M$, $bst[i][j]$ însemnând numărul maxim de bomboane culese ştiind că ne aflăm în camera $j$ unde am cules cutia $i$. De cine depinde această stare? Ştim că $bst[i - 1][1 ... N]$ a fost deja calculat în mod optim. Să notăm cu $T$ diferenţa de timp dintre momentele la care apare cutia $i$ şi cutia $i - 1$. În acest moment $i$ şi cameră $j$ putem ajunge din maxim $T$ camere spre stânga sau spre dreapta, întrucât fiecare deplasare între două camere costă o unitate de timp. De unde deducem că:
 
* $bst[i][j] = Min { bst[i - 1][j - T], bst[i - 1][j - T + 1], ..., bst[i - 1][j], ..., bst[i - 1][j + T - 1], bst[i - 1][j + T] }$.
 
Metoda directă şi, aparent eficientă, constă în folosirea unui arbore de intervale pentru aflarea acestui minim. Însă, intervalul se deplasează, dacă vom considera indicii $j$ în ordine $1$, $2$, $3$, ... constant spre dreapta, fiind reprezentat de un şir de valori de lungime constantă în care noile elemente se introduc prin dreapta şi altele se elimină prin stânga. Vom folosi un deque de lungime $2 * T$ şi vom proceda ca în problemele precedente, eliminând poziţiile care nu sunt candidate la soluţie. Mai jos este o reprezentare grafică a acestei explicaţii.
 
p=. !deque-si-aplicatii?bcrc.png 40%!
 
Complexitatea finală: $O(M * N)$.
 
h3(#problema-7). Problema 7: '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$.

Sfârşit.
==

h3(#problema-6). Problema 6: 'Bcrc':problema/bcrc (Stelele Informaticii 2006)
 
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$.
 
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 $bst[i][j]$ numărul maxim de bomboane culese până în momentul $i$ când ne găsim în camera $j$. O observaţie evidentă este că $bst[i][j]$ 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 $M$, $bst[i][j]$ însemnând numărul maxim de bomboane culese ştiind că ne aflăm în camera $j$ unde am cules cutia $i$. De cine depinde această stare? Ştim că $bst[i - 1][1 ... N]$ a fost deja calculat în mod optim. Să notăm cu $T$ diferenţa de timp dintre momentele la care apare cutia $i$ şi cutia $i - 1$. În acest moment $i$ şi cameră $j$ putem ajunge din maxim $T$ camere spre stânga sau spre dreapta, întrucât fiecare deplasare între două camere costă o unitate de timp. De unde deducem că:
 
* $bst[i][j] = Min { bst[i - 1][j - T], bst[i - 1][j - T + 1], ..., bst[i - 1][j], ..., bst[i - 1][j + T - 1], bst[i - 1][j + T] }$.
 
Metoda directă şi, aparent eficientă, constă în folosirea unui arbore de intervale pentru aflarea acestui minim. Însă, intervalul se deplasează, dacă vom considera indicii $j$ în ordine $1$, $2$, $3$, ... constant spre dreapta, fiind reprezentat de un şir de valori de lungime constantă în care noile elemente se introduc prin dreapta şi altele se elimină prin stânga. Vom folosi un deque de lungime $2 * T$ şi vom proceda ca în problemele precedente, eliminând poziţiile care nu sunt candidate la soluţie. Mai jos este o reprezentare grafică a acestei explicaţii.
 
p=. !deque-si-aplicatii?bcrc.png 40%!
 
Complexitatea finală: $O(M * N)$.
 

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