Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2009-03-29 11:19:13.
Revizia anterioară   Revizia următoare  

Deque şi aplicaţii

(Categoria Structuri de date, Autor Marius Stroe)

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

Descrierea structurii

Structura de deque (pronunţat, de obicei, deck) poate fi privită ca o listă cu două capete prin intermediul cărora se şterg sau inserează noi elemente. În literatura de specialitate aceste capete se numesc head şi tail, iar deque-ul mai este recunoscut şi ca fiind o coadă cu două capete (double ended queue).

Pentru implementarea unui deque putem recurge la liste dublu înlănţuite sau la un vector static când se cunoaşte numărul elementelor din colecţie. Limbajul C++ pune şi el la dispoziţia programatorilor o implementare prin intermediul containerului std::deque din headerul <deque>.

Operaţii:

Vom putea utiliza această structură de date în situaţiile când avem nevoie de următoarele operaţii (sunt listate cu numele sub care se găsesc în limbajul C++):

  • front()
întoarce primul element
  • back()
întoarce ultimul element
  • push_front()
inserează un element în faţă
  • push_back()
inserează un element în spate
  • pop_front()
scoate primul element
  • pop_back()
scoate ultimul element
  • empty()
întoarce true dacă în deque nu se găseşte niciun element şi false în caz contrar

Toate aceste operaţii se execută în timp O(1) pe o structură implementată de la zero sau în timp O(1) amortizat pentru containerul deque din C++.

În multe aplicaţii unde soluţiile parţiale se reprezintă sub forma unui şir continuu de valori care permite inserarea şi ştergerea doar pe la capete se poate folosi un deque. Să urmărim în continuare cazuri concrete în care simplitatea unui deque duce la soluţii de multe ori optime şi implementări foarte scurte şi clare. Aplicaţiile sunt prezentate în ordinea crescătoare a dificultăţii şi din acest motiv le recomand cu căldură tuturor celor care învaţă din acest articol să le parcurgă în ordine.

1. Book Pile (SGU)

Se dau N cărţi aşezate una deasupra celeilalte asupra cărora se vor efectua 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). Rotaţia presupune inversarea celor K elemente, adică ultimul va fi primul, penultimul va fi al doilea etc. 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.

Soluţie:

Soluţia problemei se poate deduce pe baza observaţiei următoare: odată avansată dincolo de poziţia K, o carte ajunge pe poziţia finală, întrucât orice operaţie ulterioară (inserare sau rotaţie) nu o va mai afecta. Să presupunem că iniţial avem cărţile A B C şi K = 3. Dacă îl vom adăuga pe D, atunci nu avem nevoie pentru operaţiile următoare decât de cărţile D A B, deoarece, dacă vom roti ulterior primele K cărţi, C nu va mai fi niciodată considerat. După o rotaţie, noua ordine va fi B A D şi C va fi pe raft la loc sigur. Dacă îl vom adăuga pe E, topul se va schimba în E B A, iar pe raft, în mod sigur vor fi D C, în această ordine. Cele K cărţi din vârf se prezintă ca o secvenţă continuă de elemente, la care se adaugă noi elemente sau se elimină dintre acestea numai pe la capete. Aceste capete sunt chiar head şi tail ale unui deque.

La final, când se vor termina operaţiile, cărţilor de pe raft li se vor adăuga cele din deque şi se va afişa soluţia. În cazul presupus, soluţia va fi: E B A D C.

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

2. Vila 2 (.campion, 2005)

Se dă un şir S de N numere întregi şi D un număr natural. Se cere să se determine diferenţa maximă dintre oricare două numere din şir cu proprietatea că diferenţa în modul a poziţiilor pe care se găsesc în şirul S nu depăşeşte D.
Restricţii: 2 ≤ N ≤ 100 000, 1 ≤ D ≤ N/2.

Soluţie:

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.

Algoritmul este:
    ret = 0;
    pentru i = 1, N execută
        pentru j = Max(1, i - D), i execută
            dacă ret < |S[i] - S[j]| atunci
                ret = |S[i] - S[j]|;
        sfârşit_pentru;
    sfârşit_pentru;
    return ret;
Sfârşit.

Complexitatea algoritmului este O(N2), 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ă 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].

Observaţie: Fie i1, i2 doi indici astfel încât i - D ≤ i1 < i2 ≤ i.

  1. Dacă S[i1] ≤ S[i2] atunci, cât timp cei doi indici vor fi în intervale de tipul [i - D, i], valoarea de pe poziţia i2 va fi întotdeauna preferată valorii de pe poziţia i1. Când se ajunge la un interval care nu-l mai conţine pe i1, i2 rămâne în continuare preferat.
  2. Dacă S[i1] > S[i2] atunci şi valoarea de pe poziţia i1 şi cea de pe poziţia i2 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: Ti = S[i1] > S[i2] > ... > S[iK], unde S[i1] elimină toate elementele S[j], cu S[j] ≤ S[i1] şi i - D ≤ j < i1, S[i2] elimină toate elementele S[j], cu S[j] ≤ S[i2] şi i1 < j < i2, S[i3] elimină toate elementele S[j], cu S[j] ≤ S[i3] şi i2 < j < i3 ş.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 Ti are următoarele proprietăţi:

  • se termină pe poziţia curentă, adică are loc egalitatea iK = 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 Ti+1 ştergând din indicii i1, i2 ... atâta timp cât nu se găsesc în intervalul curent şi vom şterge din poziţiile iK, iK-1 ... cât timp S[i + 1] ≥ S[iK], S[i + 1] ≥ S[iK-1] ...

Şirul Ti poate fi păstrat prin intermediul şirului de indici i1 < i2 < ... < iK. 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:

  •  \langle \widehat{5\ [1]} \rangle ;
  •  \langle 5\ [1] \rangle \Leftarrow 9\ [2] de unde se obţine  \langle \widehat{9\ [2]} \rangle ;
  •  \langle 9\ [2] \rangle \Leftarrow 4\ [3] de unde se obţine  \langle \widehat{9\ [2]},\ 4\ [3] \rangle ;
  •  \langle 9\ [2],\ 4\ [3] \rangle \Leftarrow 7\ [4] de unde se obţine  \langle \widehat{9\ [2]},\ 7\ [4] \rangle ;
  •  9\ [2] \Leftarrow \langle 7\ [4] \rangle \Leftarrow 4\ [5] de unde se obţine  \langle \widehat{7\ [4]},\ 4\ [5] \rangle ;
  •  \langle 7\ [4],\ 4\ [5] \rangle \Leftarrow 1\ [6] de unde se obţine  \langle \widehat{7\ [4]},\ 4\ [5],\ 1\ [6] \rangle ;

Cum fiecare indice din 1, 2, ..., N este adăugat şi şters cel mult o dată din deque, complexitatea finală este O(N).

3. Şir

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.

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 considera toate secvenţele candidate la rezultatul final, 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 N) cu un arbore de intervale, iar dacă diferenţa dintre acestea nu depăşeşte Z vom compara rezultatul cu cel obţinut până în acel moment. Complexitatea finală va fi O(N * (Y - X) * log N).

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 şi i - X astfel încât secvenţa [j, i] să fie candidată la soluţie. Ce proprietăţi are indicele j?

  • i - Y ≤ j ≤ i - X şi MAX - MIN ≤ 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 + 1 - Y sau MAX - MIN > Z), ori să corespundă şi atunci este cel mai mic care să respecte proprietăţile pentru i + 1.

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

Să 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:

Observaţie: Fie [j, i] un interval de interes şi i1 şi i2 doi indici astfel încât j ≤ i1 < i2 ≤ i. Atunci, dacă S[i1] ≤ S[i2] poziţia i2 va fi întotdeauna preferată poziţiei i1 atâta timp cât cele două poziţii vor fi în acelaşi interval de interes. Aşadar putem renunţa la i1 pentru etapele următoare, eliminându-l. Dacă, însă, S[i1] > S[i2], atunci poziţia i1 "va umbri" poziţia i2 atâta timp cât cele două poziţii vor fi în intervalul de forma [j, i]. În schimb, când i1 va fi eliminat, i2 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.

Rezultă din această observaţie, analog problemei anterioare, că în intervalul [j, i] se va forma un şir de poziţii i1 < i2 < ... < ik astfel încât S[i1] > S[i2] > .. > S[ik], din care extragem MAX ca fiind S[i1]. Folosind iarăşi structura de date deque, complexitatea algoritmului va fi O(N).

În pseudocod, algoritmul va arăta în felul următor:

// S = şirul de numere iniţial şi N = lungimea sa

Subalgoritmul push_in(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(deque, întreg j) este:
    cât timp (!deque.empty() şi deque.front() <= j) execută
        deque.pop_front();
    return S[deque.front()];
Sfârşit;

Algoritmul este:
    lg = 0;
    pentru i = 1, N execută
        // funcţia min(a, b) întoarce true dacă a < b
        inserează(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ă
            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;
    sfârşit_pentru

    dacă (lg > 0) atunci
        scrie lg, start, stop;
    altfel
        scrie -1;
Sfârşit.

4. Platforma (.campion, 2009)

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ă.
Restricţii: 1 ≤ M, N ≤ 1000, 1 ≤ R ≤ M, 1 ≤ C ≤ N.

Soluţie:

Această problemă reprezintă o extindere în două dimensiuni a problemei anterioare Vila 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 Maxi,j egal cu maximul dintre elementele Pi,j, Pi+1,j,.. Pi+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 Maxi,1, Maxi,2, Maxi,3,.. Maxi,j,.. Maxi,N-1, Maxi,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 Maxi,j ca fiind maximul dintre Pi,j, Pi+1,j,.. Pi+R-1,j. Rezultă că Maxi+1,j este maximul dintre Pi+1,j, Pi+2,j,.. Pi+R-1,j, Pi+R,j, adică maximul dintre elementele lui Maxi,j din care scoatem Pi,j şi adăugăm Pi+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).

5. Trans (ONI 2004)

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 Ki blocuri de piatră la un moment dat şi pentru un transport se percepe taxa Ti. 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 Si ce trebuie plătită pentru a-i schimba culoarea Ci.
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 ≤ N ≤ 16 000, 1 ≤ Q ≤ 100, 1 ≤ Ki ≤ N.

Soluţie:

Soluţia problemei se bazează pe găsirea unei formule de recurenţă ce respectă principiul optimalităţii al metodei programării dinamice.

Pentru început, fixăm un camion dintre cele  Q . Fie  K numărul maxim de pietre pe care acesta le poate transporta şi  T taxa percepută. Notăm  sum_{i,c} costul pentru a schimba toate pietrele  1, 2, \ldots, i în culoarea  c ( c = 0 pentru alb şi  c = 1 pentru negru). Rezultă că în  sum_{i,c} se vor însuma toate valorile  S_{j} , cu  j \le i pentru care  C_{j} = 1 - c .

În continuare, considerăm  bst_{i,c} costul minim pentru a transporta pietrele  1, 2, \ldots, i , iar ultimul transport conţine pietre de culoare  c . Întrucât nu putem transporta mai mult de  K pietre,  bst_{i,c} depinde doar de poziţiile  i - K, i - K + 1, \ldots, i - 1 . Cunoaştem că ultimul camion va transporta o secvenţă continuă de pietre începând de la o poziţie  j + 1 până la poziţia  i , unde  i - K \le j \le i - 1 . Astfel, pentru fiecare  j în intervalul precedent, costul va fi  Min(bst_{j,0}, bst_{j,1}) (transportăm primele  j pietre cât mai ieftin) adunat cu  sum_{i,c} - sum_{j,c} (costul transformării pietrelor  j + 1, \ldots, i în culoarea  c ) şi plus taxa  T . Rezultă recurenţa:

  •  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\ \};

Dacă ne vom opri aici, complexitatea soluţiei va fi  O(Q * N^{2}) .

Relaţia de recurenţă poate fi îmbunătăţită. Observăm că pentru poziţia  i ,  sum_{i,c} este o valoare constantă, ca şi  T . Astfel, deducem următoarea relaţie de recurenţă:

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

Notez în continuare, pentru uşurinţă în scriere,  T_{j,c} = Min(bst_{j,0}, bst_{j,1}) - sum_{j,c} . Să fixăm doi indici  i_{1} şi  i_{2} , astfel încât  i - K \le i_{1} < i_{2} \le i - 1 . Dacă  T_{i_{1},c} > T_{i_{2},c} atunci întotdeauna poziţia  i_{2} va fi preferată poziţiei  i_{1} . Când cele două nu se vor mai afla ambele în intervalul  [i - K, i - 1] , poziţia eliminată va fi poziţia  i_{1} . Dacă  T_{i_{1},c} < T_{i_{2},c} , 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  [i - K, i - 1] vom avea o serie de indecşi candidaţi la minim  i - K \le i_{1} < i_{2} < \ldots < i_{n} \le i - 1 astfel încât  T_{i_{1},c} < T_{i_{2},c} <  .. < T_{i_{n},c} . Mai departe, găsim  bst_{i,c} = T_{i_{1},c} + sum_{i,c} + T . Urmează să îl introducem şi pe  T_{i,c} în şirul de indecşi de mai sus, el fiind egal cu  Minim(bst_{i,0}, bst_{i,1}) - sum_{i,c} . Acest lucru se va face în felul următor: se vor elimina din  i_{n}, , i_{n-1}, \ldots atâta timp cât  T_{i_{n},c} > T_{i,c} ,  T_{i_{n-1},c} > T_{i,c} \ldots adică atâta timp cât poziţia  i este preferată lui  i_{n}, i_{n-1}, \ldots . Fiind la poziţia  i + 1 , intervalul se va transforma în  [i - K + 1, i] , aşadar, vom mai elimina din primii indici  i_{1}, i_{2}, \ldots atâta timp cât  i_{1} < i - K + 1, i_{2} < i - K + 1, \ldots .

După cum am arătat şi la problema precedentă, acest şir de indecşi  i_{1}, i_{2}, \ldots, i_{n} 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  1, 2, \ldots, N va trece o singură dată prin deque, complexitatea soluţiei va fi  O(N) pentru fiecare camion, deci  O(Q * N) în total.

În practică, programul este scurt, clar şi eficient:

#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;

const char iname[] = "trans.in";
const char oname[] = "trans.out";

#define MAXN  16005
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define FOR(i, a, b)  for (int i = (a); i <= (b); ++ i)

int C[MAXN], S[MAXN], bst[MAXN][2], sum[MAXN][2], N;

void insert(deque < pair <int, int> >& deq, const pair <int, int>& p) {
    while (!deq.empty() && deq.back().second > p.second)
        deq.pop_back();
    deq.push_back(p);
}

int query(deque < pair <int, int> >& deq, const int idx) {
    while (deq.front().first < idx)
        deq.pop_front();
    return deq.front().second;
}

int work(const int K, const int T) {
    deque < pair <int, int> > deq[2];       // pair (idx, value)
    FOR (c, 0, 1)
        insert(deq[c], pair <int, int>(0, 0));
    FOR (i, 1, N) {   // obiectul i
        FOR (c, 0, 1) // culoare
            bst[i][c] = query(deq[c], i - K) + sum[i][c] + T;
        FOR (c, 0, 1)
            insert(deq[c], pair <int, int>(i, Min(bst[i][0], bst[i][1]) - sum[i][c]));
    }
    return Min(bst[N][0], bst[N][1]);
}

int main(void)
{
    ifstream in(iname);  ofstream out(oname);
    in >> N;
    FOR (i, 1, N) {
        in >> C[i] >> S[i];
        FOR (c, 0, 1)
            sum[i][c] += sum[i - 1][c];
        sum[i][1 - C[i]] += S[i];
    }
    int cnt, K, T;
    in >> cnt;
    FOR (i, 1, cnt)
        in >> K >> T, out << work(K, T) << "\n";

    in.close(), out.close();
    return 0;
}

6. Otilia (.campion, 2005)

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.

Soluţie (Silviu Ganceanu):

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.

Observaţia 1: „Dacă există strategie sigură de câştig pentru stare(X, Y) atunci există şi pentru orice stare(X, T) cu T ≥ Y.”

De ce? Pentru că orice mutare validă pentru stare(X, Y) este validă şi pentru stare(X, T). Având această observaţie notăm cu MinY[X] = Y, Y minim astfel încât avem strategie de câştig pentru stare(X, Y).

Observaţia 2: „stare(X, Y) este pierzătoare dacă şi numai dacă Y < MinY[X].”

Aceasta reiese din definiţia lui MinY[X].

MinY[X] se calculează după următoarea recurenţă, care rezultă din regulile jocului:

  • MinY[X] este cel mai mic i pentru care avem MinY[X - i] > P * i.

De aici se naşte prima soluţie, care este implementarea directă a recurenţei. Deşi complexitatea acesteia pare a fi O(N2) ea se comportă foarte bine pentru N ≤ 500 000. Aşadar, această soluţie acoperă aproximativ 50% din testele de intrare. Printr-o rafinare a acestei soluţii se obţine un algoritm de complexitate O(N). Rafinarea se bazează pe:

Observaţia 3: „Să presupunem că dorim să calculăm MinY[X]. Facem următoarea afirmaţie: orice poziţie rea pentru X (în care dacă mutăm pierdem) va fi rea şi pentru X + 1.”

Acest lucru este simplu de observat dacă privim ce înseamnă că o poziţie Q e rea pentru X:

  • MinY[Q] > X - Q, pentru X;
  • MinY[Q] > X - Q + 1, pentru X + 1.

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.

7. Bcrc (Stelele Informaticii, 2006)

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.

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 \ldots 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 această stare,  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}, \ldots,\ bst_{i-1,j}, \ldots,\ 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  [j-T,j+T] se deplasează constant spre dreapta, dacă vom considera indicii  j în ordine  1, 2, 3, \ldots . Î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  T * 2 + 1 cu care vom elimina poziţiile care nu sunt candidate la soluţie. Mai jos este o reprezentare grafică a acestei explicaţii.

Complexitatea finală:  O(M * N) .

8. Cut the Sequence (PKU)

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 ≤ Si ≤ 1 000 000.

Soluţie:

Şi această soluţie foloseşte metoda programării dinamice. Construim  bst_{i} egal cu costul minim de a împărţi primele  i numere din  S . Pentru a calcula  bst_{i} alegem toate secvenţele posibile care încep la o poziţie  j+1 ,  j < i , şi adunăm valorile corespunzătoare:

  •  bst_{i} = Min\{bst_{j} + Max\{S_{j+1},.., S_{i}\}\ :\ 0 \le j < i, \displaystyle\sum_{k=j+1}^{i} S_{k} \le M\};

Implementarea directă a acestei recurenţe conduce la un algoritm de complexitate  O(N^{2}) , dar care pentru restricţiile impuse nu este de ajuns.

Să obţinem în continuare alte informaţii. Fie indicele  j minim astfel încât  \displaystyle\sum_{k=j+1}^{i} \le M . Maximul obţinut din mulţimea  \{S_{j+1},.., S_{i}\} se găseşte pe o poziţie  j^{'} unde  j < j^{'} \le i . Însă, orice indice  k cu  j \le k < j^{'} are proprietatea că rezultatul expresiei  Max\{S_{k+1},.., S_{i}\} se găseşte pe poziţia  j^{'} . Rezultă că  \forall k \in \{j, j+1,.., j^{'}-1\} ,  bst_{i} poate fi îmbunătăţit cu valoarea  bst_{k} + S_{j^{'}} . Minimul mulţimii  \{bst_{k} + S_{j^{'}} : \forall k \in \{j, j+1,.., j^{'}-1\}\} este egal cu minimul expresiei  \{bst_{k} : \forall k \in \{j, j+1,.., j^{'}-1\}\} + S_{j^{'}} (*) , deci, schimbând reperele, pentru maximul de pe poziţia  j^{'} , dacă lungimea secvenţei care se termină în  i este cel puţin  i-j^{'}+1 , atunci optimul se obţine calculând rezultatul expresiei  (*) . Pentru minimul pe un interval,  [j, j^{'}-1] al valorile vectorului  bst , putem folosi un arbore de intervale pentru  O(log_{2}N) pe interogare.

Dar, lungimea optimă a ultimei secvenţe ce se termină în  i poate fi mai mică decât  i-j^{'}+1 , deci poate fi cel mult  i-j^{'} . Optimul se găseşte printre elementele mulţimii  \{bst_{k} + Max\{S_{k+1},..,S_{i}\} : j^{'} \le k < i\} . Dacă procedăm ca la pasul anterior vom obţine un alt indice  j^{''} cu aceleaşi proprietăţi pentru secvenţa  [j^{'}, i] precum  j^{'} pentru secvenţa  [j, i] .

Inductiv obţinem un şir de indici  j_{0} = j < j_{1} < j_{2} < .. < j_{K} = i astfel încât  S_{j_{1}} este cel mai mare element al secvenţei  (j, i] ,  S_{j_{2}} cel mai mare element al secvenţei  (j_{1}, i] , şi aşa mai departe, când  j_{K} este chiar  i .

Cu ajutorul relaţiei  (*) şi a şirului  j_{1} < j_{2} < .. < j_{K} = i vom construi un alt vector  iMin cu proprietatea că  iMin_{p} = Min\{bst_{r} + S_{j_{p}} : j_{p-1} \le r < j_{p}\} . În final,  bst_{i} = Minim\{iMin_{1}, iMin_{2}, .., iMin_{K}\} , rezultat pe care îl putem obţine în  O(log_{2}N) dacă folosim un arbore de intervale.

Însă, cum se construieşte şirul  j_{1} < j_{2} < .. < j_{K} = i ? În a doua problemă am construit cu ajutorul unui deque exact şirul de indici de care avem nevoie aici. Când vom înainta la indicele  i + 1 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  bst_{i} lucru care implică combinarea structurilor de deque şi arbore de intervale. Arborele de intervale reţine valorile lui  iMin pentru fiecare element al dequelui.

Pentru a înţelege cum funcţionează acest algoritm să considerăm ca date de intrare şirul  S = \{5, 9, 4, 7, 4, 1, 6, 3\} şi  M = 15 . Perechile din deque sunt de forma  (S_{i}, iMin_{p}) . Fie  i = 1, 2, \ldots 8 :

  •  i = 1: j = 0, head = 1, tail = 1, deque = \{\ (5, 0)\ \} \Rightarrow bst_{1} = 5;
  •  i = 2: j = 0, head = 1, tail = 1, deque = \{\ (9, 0)\ \} \Rightarrow bst_{2} = 9;
  •  i = 3: j = 1, head = 1, tail = 2, deque = \{\ (9, 5),\ (4, 9)\ \} \Rightarrow bst_{3} = 13;
  •  i = 4: j = 2, head = 2, tail = 2, deque = \{\ (7, 9)\ \} \Rightarrow bst_{4} = 16;
  •  i = 5: j = 2, head = 2, tail = 3, deque = \{\ (7, 9),\ (4, 16)\ \} \Rightarrow bst_{5} = 16;
  •  i = 6: j = 3, head = 2, tail = 4, deque = \{\ (7, 13),\ (4, 16),\ (1, 16)\ \} \Rightarrow bst_{6} = 17;
  •  i = 7: j = 4, head = 3, tail = 3, deque = \{\ (6, 16)\ \} \Rightarrow bst_{7} = 22;
  •  i = 8: j = 4, head = 3, tail = 4, deque = \{\ (6, 16),\ (3, 22)\ \} \Rightarrow bst_{8} = 22;

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  i = 6 .

Numărul maxim de elemente ce pot trece prin deque este 8. În figură, arborele ţine minimul de pe poziţiile 2, 3, 4 din deque.

Algoritmul în pseudocod arată în felul următor:

Algoritmul este:
    sum  = 0;
    last = 0;
    // indicii head si tail ai dequeului
    head = tail = 1;
    // poziţia lui bst[0] se inserează în deque
    deque[1] = 0;
    pentru i = 1, N execută
        sum += S[i];
        temp = bst[ deque[tail] ];
        cât timp (head <= tail) şi (S[ deque[tail] ] <= S[i]) execută
            temp = Min(temp, iMin[tail]);
            tail --;
        sfârşit;
        // adaug poziţia i la deque
        tail ++;
        deque[tail] = i;
        // actualizez iMin[]
        iMin[tail]  = temp;
        // actualizez T[], arborele de intervale pe deque[]
        Update(T, tail, iMin[tail] + S[i]);
        // suma valorilor din [last, i] trebuie să nu depăşească M
        cât timp (sum > M) execută
            sum -= S[last];
            dacă (deque[head] == last) atunci
                head ++;
            sfârşit;
            last ++;
        sfârşit;
        // actualizez iMin[], Tb[] arborele de intervale pe bst[]
        iMin[head] = Query(Tb, Max(last - 1, 0), deque[head] - 1);
        // actualizez T[]
        Update(T, head, iMin[head] + S[ deque[head] ]);
        // reţin optimul pentru poziţia curentă
        bst[i] = Query(T, head, tail);
        // actualizez Tb[]
        Update(Tb, i, bst[i]);
    sfârşit;
    scrie bst[N];
Sfârşit.

Complexitatea finală este  O(N*log_{2}N) .

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

Probleme suplimentare

Înţelegerea profundă nu se poate realiza decât prin rezolvarea a cât mai multe probleme. Succes!

Bibliografie

  1. Cosmin Negruşeri, Probleme cu secvenţe
  2. Dana Lica, Arbori de intervale şi aplicaţii în geometria computaţională
  3. Cătălin Frâncu, Heapuri
  4. Marius Stroe, Treapuri
  5. C++ Reference