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$. Destul de eficient. Să vedem cum putem îmbunătăţi complexitatea $O(log{~2~}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{~2~}N)$ la $O(1)$ amortizat este următoarea: „Fixăm $i{~1~}$ şi $i{~2~}$ astfel încât $j < i{~1~} < i{~2~} &le; i$. Atunci, dacă $S[i{~2~}] > S[i{~1~}]$ poziţia $i{~2~}$ va fi întotdeauna mai importantă decât poziţia $i{~1~}$ atâta timp cât cele două poziţii vor fi în intervalul $(j, i]$. Când $i{~1~}$ şi $i{~2~}$ nu vor mai fi în intervalul $(j, i]$, poziţia eliminată va fi {$i{~1~}$}”. Rezultă din această observaţie că în intervalul $(j, i]$ poziţiile importante vor fi $j < i{~1~} < i{~2~} < .. < i{~k~} <= i$ astfel încât $S[i{~1~}] > S[i{~2~}] > .. > S[i{~k~}]$. Astfel $MAX$ va fi $S[i{~1~}]$. 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{~1~}$, $i{~2~}$, ... 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{~1~}, i{~2~}, .., 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ă.

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{~2~}N)$ la $O(1)$ amortizat este următoarea:
 
_Observaţie_: Fixăm $i{~1~}$ şi $i{~2~}$ astfel încât $j < i{~1~} < i{~2~} &le; i$. Atunci, dacă $S[i{~2~}] > S[i{~1~}]$ poziţia $i{~2~}$ va fi întotdeauna mai importantă decât poziţia $i{~1~}$ atâta timp cât cele două poziţii vor fi în intervalul $(j, i]$. Când $i{~1~}$ şi $i{~2~}$ nu vor mai fi în intervalul $(j, i]$, poziţia eliminată va fi {$i{~1~}$}.
 
Rezultă din această observaţie că în intervalul $(j, i]$ poziţiile importante vor fi $j < i{~1~} < i{~2~} < .. < i{~k~} <= i$ astfel încât $S[i{~1~}] > S[i{~2~}] > .. > S[i{~k~}]$. Astfel $MAX$ va fi $S[i{~1~}]$. 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{~1~}$, $i{~2~}$, ... 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{~1~}, i{~2~}, .., 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:

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

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

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.
Restricţii: $1 ≤ M ≤ 30 000$, $1 ≤ N ≤ 5 000 000$, $1 ≤ K ≤ N$, $1 ≤ P ≤ 10$.
 
h3. 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^2^)$ ea se comportă foarte bine pentru $N &le; 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 trece la pasul următor. Aceste operaţii se pot implementa cu ajutorul unui deque.

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