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

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

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

h2(#bibliografie). Bibliografie

# 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

# 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

# 'C++ Reference':http://www.cplusplus.com/