Deque şi aplicaţii

(Categoria Structuri de date, Autor Xulescu)

• Conţinut:
• Introducere
• Operaţii
• Aplicaţii
  • Problema 1: Book Pile (SGU)
  • Problema 2: Şir
  • Problema 3: Trans (ONI 2004)
  • Problema 4: Otilia (.campion)
  • Problema 5: Cut the Sequence (PKU)
  • Problema 6: Bcrc (Stelele Informaticii 2006)
• Concluzii
• Probleme suplimentare
• Bibliografie

În acest articol voi prezenta o structură de date de tip listă numită deque. Simplitatea acestei structuri poate nu are multe de spus şi din acest motiv am prezentat şi o serie de aplicaţii care vor arăta neaşteptata sa utilitate şi apariţie în locurile unde am fi crezut că nu se mai poate face nimic pentru a reduce complexitatea.

Introducere

Dequeul (pronunţat de obicei deck) poate fi privit ca o colecţie de tip listă ce are două capete prin care se şterg sau inserează noi elemente. În literatura de specialitate, aceste capete se numesc head şi tail, iar dequeul mai este recunoscut şi ca fiind o coadă cu două capete (double ended queue).

Un deque poate fi implementat folosind liste dublu înlănţuite, sau cu un vector static când se cunoaşte numărul elementelor din colecţie. Ce trebuie reţinut este că limbajul C++ pune la dispoziţia utilizatorilor prin intermediul headerului #include <deque> clasa std::deque.

Operaţii

Mai jos sunt operaţiile care pot fi efectuate asupra unui deque, iar în stânga corespondentul lor î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ă dequel este gol.

Toate aceste operaţii se execută în timp O(1) amortizat. Pentru un plus de viteză va trebui să folosim un vector static cu dimensiunea egală cu numărul maxim de elemente ce pot trece prin deque, iar operaţiile implementate „de mână”, cu doi indecşi ce indică către head şi tail. Însă, în majoritatea aplicaţiilor limita de timp permite folosirea lejerităţii şi siguranţei clasei std::deque.

Aplicaţii

Folosiţi deque! Foarte sănătos! :)

Problema 1: Book Pile (SGU)

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.

Soluţie:

Soluţia problemei se poate deduce urmând paşii următori. Să presupunem că avem cărţile A B C iniţial şi K = 3. Dacă îl vom adăuga pe D, atunci nu vor rămâne importante decât cărţile D A B, deoarece, dacă vom roti ulterior ultimele K cărţi, C nu va mai fi niciodată considerat, cărţile fiind doar adăugate, iar o dată ce o carte iese din „top K” cărţi nu va mai fi posibil să i se schimbe poziţia pe raft. Să rotim acum „top K” cărţi. Noua ordine va fi B A D şi C 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, în această ordine, D C. Proprietatea celor K cărţi din vârf este: 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 O(1) amortizat, soluţia are complexitatea O(N + M).

Problema 2: Sir

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

Să presupunem că pentru poziţia curentă i, l-am găsit pe j cuprins între i - Y şi i - X care îndeplineşte optimul. Ce proprietăţi are j?

• i - Y ≤ j ≤ i - X şi MAX - MIN ≤ Z;
• dacă îl incrementăm pe j la j + 1 atunci dacă j ≤ i - X cu siguranţă MAX - MIN ≤ 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.

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₂(Y)).

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 dată cu j. Să vedem cum putem îmbunătăţi complexitatea O(log₂Y) pentru determinarea maximului şi minimului.

Pentru fixarea ideilor să urmărim cum îl calculăm pe MAX. Observaţia care ne ajută în multe probleme pentru reducerea complexităţii de la O(log₂N) la O(1) amortizat este următoarea:

Observaţie: „Fixăm i₁ şi i₂ astfel încât j < i₁ < i₂ ≤ i. Atunci, dacă S[i₂] > S[i₁] poziţia i₂ va fi întotdeauna mai importantă decât poziţia i₁ atâta timp cât cele două poziţii vor fi în intervalul (j, i]. Când i₁ şi i₂ nu vor mai fi în intervalul (j, i], poziţia eliminată va fi i₁.”

Rezultă din această observaţie că în intervalul (j, i] poziţiile importante vor fi j < i₁ < i₂ < .. < i_k <= i astfel încât S[i₁] > S[i₂] > .. > S[i_k]. Astfel, MAX va fi S[i₁]. 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₁, i₂, ... 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₁, i₂, .., i_k este că se reprezintă ca un şir contiguu 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ă, programul poate arăta în felul următor:

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

#define MAXN  100005

typedef int (*PF)(const int , const int ) ;

int V[MAXN];  

deque <int> min_deq, max_deq;


int min_fct(const int a, const int b) { return a < b; }

int max_fct(const int a, const int b) { return a > b; }

void push_in(deque <int>& deq, const int p, PF compare) {
    for (; !deq.empty() && compare(V[p], V[deq.back()]); deq.pop_back()) ;
    deq.push_back(p);
}

int query(deque <int>& deq, const int j) {
    for (; !deq.empty() && deq.front() <= j; deq.pop_front()) ;
    return V[deq.front()];
}

int main(void)
{
    ifstream in("sir.in");  ofstream out("sir.out");
    int n, X, Y, Z;
    int length = 0, start, stop, j = 0;

    in >> n >> X >> Y >> Z;
    for (int i = 1; i <= n; ++ i) {
        in >> V[i];
        push_in(min_deq, i, min_fct);
        push_in(max_deq, i, max_fct);
        while ((j < i - Y || query(max_deq, j) - query(min_deq, j) > Z) && j < i - X)
            j ++;
        // (j, i] este intervalul candidat la soluţia pentru pozitia i
        if (j <= i - X) if (query(max_deq, j) - query(min_deq, j) <= Z)
            if (i - j >= length)
                length = i - j, start = j + 1, stop = i;
    }
    length > 0 ? out << length << " " << start << " " << stop : out << -1;
    in.close(), out.close();
    return 0;
}

Complexitatea finală va fi O(N).

Problema 3: 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 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.
Restricţii: 1 ≤ N ≤ 16 000, 1 ≤ Q ≤ 100, 1 ≤ K_i ≤ 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, .., i în culoarea c (c = 0 pentru alb şi c = 1 pentru negru). În sum[i][c] se vor aduna toate valorile S[j], cu j ≤ i pentru care C[j] = 1 - c.

În continuare, considerăm bst[i][c] costul minim pentru a transporta pietrele 1, 2, .., 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, ..., 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 ≤ j ≤ 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, .., i în culoarea c) şi plus taxa T. Rezultă recurenţa:

• bst[i][c] = Min{ Min(bst[j][0], bst[j][1]) + sum[i][c] - sum[j][c] } + T, unde i - K ≤ j ≤ i - 1.

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

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{ Min(bst[j][0], bst[j][1]) - sum[j][c] } + sum[i][c] + T, unde i - K ≤ j ≤ i - 1.

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

După cum am arătat şi la problema precedentă, acest şir de indecşi i₁, i₂, .., 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, .., N va trece o singură dată prin deque şi va fi şters cel mult o dată, complexitatea soluţiei în acest caz va fi O(Q * N).

În practică, programul poate arăta în felul următor:

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

Problema 4: Otilia (.campion)

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:

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(N²) 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.

Problema 5: Cut the Sequence (PKU)

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

Problema 6: Bcrc (Stelele Informaticii 2006)

(deque la programare dinamica)
...

Concluzii

Filozofia din spatele structurii de deque devine utilă, de obicei, în momentele finale ale rezolvării unei probleme. După cum s-a văzut în aplicaţiile precedente, dequeul ajută la îmbunătăţirea complexităţii prin eliminarea unor valori de care nu vom mai avea nevoie în viitor. Însă, ce pot spune cu certitudine este că această structură de date pe cât este de simplă pe atât este de eficientă.

Probleme suplimentare

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

• Deque, Arhiva educaţională
• Secvenţă
• Secvenţă 3
• Secvenţă 4
• Brânză
• Struţi
• Trompetă
• Buline
• Balans
• Gard, ONI 2002
• Ghiozdan
• Munte4, Lotul Naţional de Informatică, 2005
• Cover, ONI 2007, Baraj

Bibliografie

1. Cosmin Negruşeri, Probleme cu secvenţe
2. Dana Lica, Arbori de intervale şi aplicaţii în geometria computaţională