(Categoria _Structuri de date_, Autor _Xulescu_)

(toc){width: 20em}*{text-align:center} *Conţinut:*

(toc){width: 25em}*{text-align:center} *Conţinut:*

* 'Introducere':deque-si-aplicatii#introducere
* '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 6: Bcrc (Stelele Informaticii 2006)':deque-si-aplicatii#problema-6
* 'Concluzii':deque-si-aplicatii#concluzii
* 'Probleme suplimentare':deque-si-aplicatii#probleme-suplimentare
* 'Bibliografie':deque-si-aplicatii#bibliografie

În acest articol voi prezenta o structură de date de tip listă numită deque şi o serie de aplicaţii utile care vă vor demonstra simplitatea şi utilitatea folosirii acesteia, în special în concursurile de informatică.

Unde-i folosit dequeul? :-?

h3. 'Book Pile':http://acm.sgu.ru/problem.php?contest=0&problem=271 (SGU)

h3(#problema-1). Problema 1: 'Book Pile':http://acm.sgu.ru/problem.php?contest=0&problem=271 (SGU)

bq. Se dau $N$ cărţi aşezate una deasupra celeilalte asupra cărora se vor efecta $M$ operaţii de două tipuri: 1. $ADD${$(nume)$} : se adaugă cartea $nume$ deasupra celorlalte; 2. $ROTATE$ : primele $K$ cărţi de deasupra se rotesc (dacă sunt mai puţin de $K$ cărţi atunci se vor roti toate). Se cere să se afişeze cărţile în ordine, prima fiind cea de deasupra, după efectuarea celor $M$ operaţii.
Restricţii: $0 ≤ N, K ≤ 40 000$, $0 ≤ M ≤ 100 000$.

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

h3. 'Sir':problema/sir

h3(#problema-2). Problema 2: 'Sir':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$.

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

p=. !deque-si-aplicatii?sir.png 60%!

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

h3. 'Trans':problema/trans (ONI 2004)

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

(gen bun de problema)
...

h3. 'Otilia':problema/otilia  (.campion)

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

(deque la o problema de teoria jocurilor)
...

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

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

(deque cu arbori de intervale, zice Paul)
...

h3. 'Bcrc':problema/bcrc (Stelele Informaticii 2006)
 

h3(#problema-6). Problema 6: 'Bcrc':problema/bcrc (Stelele Informaticii 2006)

(deque la programare dinamica)

...

...
 
h2(#concluzii). Concluzii
 
Nicio concluzie până acum.
 
h2(#probleme-suplimentare). Probleme suplimentare
 
* 'Secventa':problema/secventa
* 'Secventa 3':problema/secv3
* 'Secventa 4':problema/secv4
* 'Branza':problema/branza
* 'Struti':problema/struti
* 'Trompeta':problema/trompeta
* 'Buline':problema/buline
* 'Balans':problema/balans
* 'Gard':problema/gard, _ONI 2002_ (Cred că ar merge mai bine la aplicaţii)
* 'Ghiozdan':problema/ghiozdan
* 'Munte4':problema/munte4, _Lotul Naţional de Informatică, 2005_
* 'Cover':problema/cover, _Baraj ONI 2007_
 
h2(#bibliografie). Bibliografie
 
# Dana Lica - "_Arbori de intervale si aplicatii in geometria computationala_":arbori-de-intervale