h3. 'Sir':problema/sir

bq. Se dă un şir 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.

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

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 - 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 $i - X < j$; 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$.

* 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 $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{~2~}(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$. Destul de eficient. Să vedem cum putem îmbunătăţi complexitatea $O(log{~2~}Y)$ pentru determinarea maximului şi minimului. În episodul următor...

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ă. Complexitatea finală va fi $O(N)$.

h3. 'Trans':problema/trans (ONI 2004)