h2(#problema-3). 3. 'Şir':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ă.
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$.
h3. 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{~2~}N)$ cu un arbore de intervale, iar daca diferenţa dintre acestea nu depăşeşte $Z$ vom compara cu rezultatul obţinut până în acel moment. Complexitatea finală va fi $O(N * (Y - X) * log{~2~}N)$.
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$?
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$;
* 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$.
* 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$.
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$ pe fiecare interval $(j, i]$, cu proprietăţile de mai sus, se poate folosi un arbore de intervale. Complexitatea finală va fi $O(N * log{~2~}(N))$.
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)$.
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{~2~}N)$ pentru determinarea maximului şi minimului.
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:
Pentru fixarea ideilor să urmărim cum îl vom calcula 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, asemănător problemei precedentă, următoarea:
_Observaţie_: Fie $[j, i]$ un interval de interes şi $i{~1~}$ şi $i{~2~}$ doi indici astfel încât $j ≤ i{~1~} < i{~2~} ≤ i$. Atunci, dacă $S[i{~1~}] ≤ S[i{~2~}]$ poziţia $i{~2~}$ va fi întotdeauna preferată poziţiei $i{~1~}$ atâta timp cât cele două poziţii vor fi în acelaşi interval de interes. Aşadar putem renunţa la $i{~1~}$ pentru etapele următoare, eliminându-l. Dacă, însă, $S[i{~1~}] > S[i{~2~}]$, atunci poziţia $i{~1~}$ "va umbri" poziţia $i{~2~}$ atâta timp cât cele două poziţii vor fi în intervalul de forma $[j, i]$. În schimb, când $i{~1~}$ va fi eliminat, $i{~2~}$ 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.
_Observaţie_: Fie $(j, i]$ un interval de interes şi $i{~1~}$ şi $i{~2~}$ astfel încât $j < i{~1~} < i{~2~} ≤ i$. Atunci, dacă $S[i{~2~}] > S[i{~1~}]$ poziţia $i{~2~}$ va fi întotdeauna preferată poziţiei $i{~1~}$ atâta timp cât cele două poziţii vor fi în acelaşi interval de interes. Când $i{~1~}$ şi $i{~2~}$ nu vor mai fi ambele în acelaşi interval poziţia eliminată va fi $i{~1~}$. Dacă însă $S[i{~1~}] > S[i{~2~}]$, atunci poziţia $i{~1~}$ va umbri poziţia $i{~2~}$ atâta timp cât cele două poziţii vor fi în intervalul $(j, i]$. Când $i{~1~}$ va fi eliminat, atunci e posibil ca $i{~2~}$ să fie un candidat la $MAX$ dintre restul elementelor de la dreapta sa. În acest caz, nu putem afirma nimic şi vom păstra cele două poziţii.
Rezultă din această observaţie, analog 'problemei anterioare':deque-si-aplicatii#problema-2, că în intervalul $[j, i]$ se va forma un şir de poziţii $i{~1~} < i{~2~} < ... < i{~k~}$ astfel încât $S[i{~1~}] > S[i{~2~}] > .. > S[i{~k~}]$, din care extragem $MAX$ ca fiind $S[i{~1~}]$. Folosind iarăşi structura de date $deque$, complexitatea algoritmului va fi $O(N)$.
Rezultă din această observaţie, analog 'problemei anterioare':deque-si-aplicatii#problema-2, că în intervalul $(j, i]$ se va forma un şir de poziţii $i{~1~} < i{~2~} < .. < i{~k~}$ astfel încât $S[i{~1~}] > S[i{~2~}] > .. > S[i{~k~}]$, din care obţinem că $MAX$ este egal cu $S[i{~1~}]$. Observaţia ne arată că indicele $i{~1~}$ elimină toate valorile mai mici decât $S[i{~1~}]$ aflate în intervalul $(j, i{~1~})$, indicele $i{~2~}$ elimină toate valorile mai mici decât $S[i{~2~}]$ aflate în intervalul $(i{~1~}, i{~2~})$ ş.a.m.d. 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 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 continuu 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ă, pseudocodul poate arăta în felul următor:
În pseudocod, algoritmul va arăta în felul următor:
== code(cpp) |
// S şirul de numere iniţial şi N lungimea sa
// 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ă
