Presupunem că orice secvenţă optimă ar avea lungimea mai mare decât $K$. Atunci putem obţine o secvenţă mai mică, cu aceeaşi bază eliminând unul din capetele unei secvenţe optime. Deci este de ajuns să cautăm secvenţele optime de lungime exact $K$.

Acum putem face o parcurgere a şirului pentru a rezolva problema. Mai întâi punem într-un $min-heap$ $K$ elemente, verificăm vârful heapului şi obţinem astfel minimul secvenţei $a[1..k]$. Apoi eliminăm elementul $a[1]$ din heap şi inserăm elementul $a[K+1]$. Prin verificarea vârfului heapului obţinem minimul secvenţei $a[2..K+1]$. Continuăm procedeul până aflăm elementul minim pentru fiecare subsecvenţă de lungime $K$ a şirului $a$ (complexitate $O(N log N)$). Există şi alte soluţii pentru găsirea elementului minim al unei subsecvenţe, precum folosirea unui arbore de intervale sau folosirea tehnicii $O(N log N)/O(1)$ pentru problema _RMQ_, dar obţinem tot soluţii de complexitate $O(N log N)$.

Acum putem face o parcurgere a şirului pentru a rezolva problema. Mai întâi punem într-un $min-heap$ $K$ elemente, verificăm vârful heapului şi obţinem astfel minimul secvenţei $a[1..K]$. Apoi eliminăm elementul $a[1]$ din heap şi inserăm elementul $a[K + 1]$. Prin verificarea vârfului heapului obţinem minimul secvenţei $a[2..K + 1]$. Continuăm procedeul până aflăm elementul minim pentru fiecare subsecvenţă de lungime $K$ a şirului $a$ (complexitate $O(N log K)$). Există şi alte soluţii pentru găsirea elementului minim al unei subsecvenţe, precum folosirea unui arbore de intervale sau folosirea tehnicii $O(N log N)/O(1)$ pentru problema _RMQ_.

O observaţie importantă este aceea că dacă vrem să vedem minimul secvenţei ce se termină în $i$ şi avem $j{~1~} < j{~2~} <= i$ şi $a[j{~1~}] >= a[j{~2~}]$, atunci evident $a[j{~1~}]$ nu va fi minimul secvenţei ce se termină în $i$. Folosim o structură de date ca la soluţia cu heapuri, care adaugă elemente noi şi şterge elemente vechi, dar pe lângă elementele ce au fost inserate acum $k$ paşi şi trebuie şterse, mai ştergem şi elementele mai noi care nu ne vor mai fi utile, după cum este $a[j{~2~}]$ mai sus. Ca structură de date folosim o listă în care putem insera şi şterge de la ambele capete, un _deque_. Fiecare element inserat în deque va fi o pereche de valori, valoarea din şir şi indexul din şir $(a[i], i)$. Când o valoare este inserată în şir, ea este pusă la capătul din dreapta al şirului, dar înainte de inserare cât timp elementul din capătul şirului are valoarea mai mare decât $a[i]$ el este eliminat. La fiecare pas după o inserţie se verifică dacă elementul din capătul din stânga este mai bătrân de $K$ iteraţii.

O observaţie importantă este aceea că dacă vrem să vedem minimul secvenţei ce se termină în $i$ şi avem $j{~1~} < j{~2~} <= i$ şi $a[j{~1~}] >= a[j{~2~}]$, atunci evident $a[j{~1~}]$ nu va fi minimul secvenţei ce se termină în $i$. Folosim o structură de date ca la soluţia cu heapuri, care adaugă elemente noi şi şterge elemente vechi, dar pe lângă elementele ce au fost inserate acum $K$ paşi şi trebuie şterse, mai ştergem şi elementele mai noi care nu ne vor mai fi utile, după cum este $a[j{~2~}]$ mai sus. Ca structură de date folosim o listă în care putem insera şi şterge de la ambele capete, un _deque_. Fiecare element inserat în deque va fi o pereche de valori, valoarea din şir şi indexul din şir $(a[i], i)$. Când o valoare este inserată în şir, ea este pusă la capătul din dreapta al şirului, dar înainte de inserare cât timp elementul din capătul şirului are valoarea mai mare decât $a[i]$ el este eliminat. La fiecare pas după o inserţie se verifică dacă elementul din capătul din stânga este mai „bătrân” de $K$ iteraţii.

Din cauza modului în care se fac inserţiile şi ştergerile, şirul va fi sortat totdeauna crescător după indecşi şi crescător după valori. Tot timpul ultimul element din stivă va conţine valoarea bazei. Acest algoritm are complexitatea $O(N)$ pentru că fiecare element este inserat şi şters din deque cel mult o dată.

h2(#prob7). Problema 7 (Agricultura, Algoritmus)

Vasilica vrea să se apuce de agricultură şi, prin urmare, să cumpere o parcelă de teren. Harta pusă la dispoziţie de către primăria oraşului în care locuieşte Vasilică se poate reprezenta sub forma unei matrice de dimensiuni $N x M (2 <= N, M <= 150)$, fiecare $m^2^$ de teren fiind reprezentat printr-un element din matrice. Pentru fiecare $m^2^$ de pământ se cunoaşte altitudinea (faţă de nivelul mării) la care se află acesta. Agricultorul nostru doreşte să cumpere o parcelă de formă dreptunghiulară dar, deoarece are de gând să se ocupe de culturi foarte pretenţioase la modificări de nivel, diferenţa dintre valorile care indică altitudinea maximă şi cea minimă din parcelă trebuie să fie mai mică decât o valoare dată $K (1 <= K <= 1 000)$. Mai mult, suprafaţa pe care Vasilică o va achiziţiona trebuie să fie cât mai mare posibil.

bq. Se dă o matrice de dimensiuni $N x M$ de numere naturale. Se cere determinarea unei submatrici cu număr maxim de celule în care diferenţa între valoarea maximă şi valoarea minimă este mai mică decât o valoare dată $K$. Restrictii: $2 <= N, M <= 150$, $1 <= K <= 1 000$.

h3. Exemplu:

h3. Rezolvare:

Problema constă în determinarea submatricei cu număr maxim de celule în care diferenţa între valoarea maximă şi valoarea minimă este mai mică decât $K$. Vom folosi ideea de la problema cu subsecvenţa de sumă maximă pe matrice, adică vom fixa două linii $i{~1~}$ şi $i{~2~}$. Acum pentru fiecare coloană $j$ păstrăm în $m[j]$ elementul minim şi în $M[j]$ elementul maxim $a[i][j]$ cu $i{~1~} <= i <= i{~2~}$. Astfel la fiecare pas trebuie acum să rezolvăm problema determinării unei subsecvenţe de lungime maximă pentru care diferenţa între elementul maxim şi minim este mai mică decât $K$. Folosind un _max-heap_ şi un _min-heap_ putem parcurge elementele şirurilor $M$ şi $m$ în ordine inserând la fiecare pas elemente în heap şi determinând cea mai lungă secvenţă ce se termină în $i$ cu proprietatea dată. Vom ţine un al 2-lea indice $j$, iniţial $0$, care atâta timp cât diferenţa între elementul maxim din max-heap cu elementul minim din min-heap este mai mare sau egală cu $K$, vom scoate din heapuri elementele $M[j]$, respectiv $m[j]$ şi îl vom incrementa pe $j$ ( complexitate $O(N^3^ log N)$ ). Dacă în loc de heapuri folosim deque-uri, atunci acest algoritm va avea complexitatea $O(N^3^)$.

Problema constă în determinarea submatricei cu număr maxim de celule în care diferenţa între valoarea maximă şi valoarea minimă este mai mică decât $K$. Vom folosi ideea de la problema cu subsecvenţa de sumă maximă pe matrice, adică vom fixa două linii $i{~1~}$ şi $i{~2~}$. Acum pentru fiecare coloană $j$ păstrăm în $m[j]$ elementul minim şi în $M[j]$ elementul maxim $a[i][j]$ cu $i{~1~} <= i <= i{~2~}$. Astfel la fiecare pas trebuie acum să rezolvăm problema determinării unei subsecvenţe de lungime maximă pentru care diferenţa între elementul maxim şi minim este mai mică decât $K$. Folosind un _max-heap_ şi un _min-heap_ putem parcurge elementele şirurilor $M$ şi $m$ în ordine inserând la fiecare pas elemente în heap şi determinând cea mai lungă secvenţă ce se termină în $i$ cu proprietatea dată. Vom ţine un al $2$-lea indice $j$, iniţial $0$, care atâta timp cât diferenţa între elementul maxim din max-heap cu elementul minim din min-heap este mai mare sau egală cu $K$, vom scoate din heapuri elementele $M[j]$, respectiv $m[j]$ şi îl vom incrementa pe $j$. Complexitate: $O(N^3^ log N)$. Dacă în loc de heapuri folosim deque-uri, atunci acest algoritm va avea complexitatea $O(N^3^)$.

h2(#prob8). Problema 8 ('Secvenţa 2':problema/secv2)

Gigel s-a decis să devină olimpic la informatică, poate aşa va reuşi să-şi rezolve singur problemele, şi nu va mai cere ajutorul vostru! La ora de informatică, profesoara lui i-a dat să rezolve problema secvenţei de sumă maximă: "Gigele, eu iţi dau un şir de $N$ numere întregi, iar tu trebuie să găseşti o secvenţă ( adică un subşir de numere care apar pe poziţii consecutive în şirul iniţial ) cu suma elementelor maximă!". După vreo $30$ de minute, Gigel s-a ridicat mândru şi a zis: "Am găsit algoritmul de complexitate optimă, doamna profesoară!". Ca temă pentru acasă Gigel are de rezolvat aproape aceeaşi problemă: trebuie să găsească secvenţa de sumă maximă de lungime cel puţin $K (1 <= k <= N <= 50 000)$. Gigel încă nu ştie destul de multă informatică ca să poata rezolva această problemă, dar poate îl ajutaţi voi! Scrieţi un program care rezolvă problema din tema lui Gigel.

bq. Se da un şir de $N$ numere întregi şi un număr natural $K$. O secvenţă este un subşir de numere care apar pe poziţii consecutive în şirul iniţial. Se cere să se găsească secvenţa de sumă maximă de lungime cel puţin $K$. Restrictii: $1 <= K <= N <= 50 000$.

h3. Exemplu:

h3. Rezolvare:

Putem folosi rezolvarea liniară bazată pe programare dinamică prezentată ca subalgoritm în soluţia problemei $5$, dar putem simplifica logica din acea rezolvare. Vom folosi şirul sumelor parţiale $sum$, iar pentru a determina subsecvenţa de sumă maximă ce se termină în $i$ şi are lungimea cel puţin $K$ trebuie să găsim $sum[j]$ minim astfel ca $j < i - K$. Parcurgem lista, şi la pasul $i$ determinăm $best[i] = sum[i] - min(sum[j])$, $j < i - K$. Comparăm minimul curent cu $sum[i-K]$ şi trecem la pasul următor. Complexitate: $O(N)$.

Putem folosi rezolvarea liniară bazată pe programare dinamică prezentată ca subalgoritm în soluţia 'problemei $5$':probleme-cu-secvente#prob5, dar putem simplifica logica din acea rezolvare. Vom folosi şirul sumelor parţiale $sum[]$, iar pentru a determina subsecvenţa de sumă maximă ce se termină în $i$ şi are lungimea cel puţin $K$ trebuie să găsim $sum[j]$ minim astfel ca $j < i - K$. Parcurgem lista, şi la pasul $i$ determinăm $best[i] = sum[i] - min(sum[j])$, $j < i - K$. Comparăm minimul curent cu $sum[i - K]$ şi trecem la pasul următor. Complexitate: $O(N)$.

h2(#prob9). Problema 9 ('Sum':problema/sum2, Stelele Informaticii 2003 )

Se dă un şir de numere întregi. Se caută un subşir cu lungimea cuprinsă între $L$ şi $U$, format din elemente consecutive ale şirului iniţial, cu suma elementelor maximă $(1 <= L <= U <= N <= 100 000)$.

bq. Se dă un şir de $N$ numere întregi. Se caută un subşir cu lungimea cuprinsă între $L$ şi $U$, format din elemente consecutive ale şirului iniţial, cu suma elementelor maximă. Restrictii: $1 <= L <= U <= N <= 100 000$.

h3. Rezolvare:

Pentru fiecare $i$ este de ajuns să aflăm valoarea expresiei $sum[i] - sum[j]$, unde $i - L > j >= i - U$. Pentru a determina valoarea optimă pentru $sum[j]$ putem folosi un heap de dimensiune $U - L$, sau putem folosi tehnici de determinare a valorii minime într-un interval dat ( complexitate $O(N log (U - L)$ ) ).

Pentru fiecare $i$ este de ajuns să aflăm valoarea expresiei $sum[i] - sum[j]$, unde $i - L > j >= i - U$. Pentru a determina valoarea optimă pentru $sum[j]$ putem folosi un heap de dimensiune $U - L$, sau putem folosi tehnici de determinare a valorii minime într-un interval dat. Complexitate: $O(N log(U - L))$.

Altă abordare de aflare a minimelor unor secvenţe de lungime dată (în cazul acesta lungimea este $U - L$ ) a fost prezentată în rezolvarea 'problemei $6$':probleme-cu-secvente@prob6. Folosind acea tehnică obţinem o rezolvare de complexitate liniară.

h2(#prob10). Problema 10 ('Secvenţa 3':problema/secv3)

Gigel este o persoană cu o imaginaţie foarte bogată, mai ales când doarme! Într-o noapte a visat că are de îndeplinit o sarcină foarte bizară: trebuie să aleagă o secvenţă (adica un subşir de elemente care apar pe poziţii consecutive în şirul iniţial) din $N$ elemente pentru care se cunosc costul şi timpul. Secvenţa aleasă trebuia să fie de lungime minim $L$ şi maxim $U$, iar suma costurilor elementelor secvenţei împărţiţă la suma timpurilor elementelor secvenţei să fie maximă $(1 <= L <= U <= N <= 30 000)$.

bq. Se dă un şir de $N$ elemente pentru care se cunosc două informaţii: costul şi timpul. O secvenţă este un subşir de numere care apar pe poziţii consecutive în şirul iniţial. Se caută o secvenţă din cele $N$ elemente care să fie de lungime minim $L$ şi maxim $U$, iar suma costurilor elementelor secvenţei împărţiţă la suma timpurilor elementelor secvenţei să fie maximă. Restrictii: $1 <= L <= U <= N <= 30 000$.

h3. Exemplu:

h3. Rezolvare:

Procedăm ca la problema $5$ şi căutăm binar valoarea optimă. Şirul va fi transformat în $b[i] = c[i] - t[i] * X$. Acum trebuie să mai rezolvăm subproblema care cere să determinăm o subsecvenţă de sumă maximă pentru care lungimea se află între $L$ şi $U$. Această subproblemă a fost soluţionată în problema anterioară, unde s-a găsit un algoritm liniar. Astfel soluţia acestei probleme are complexitatea $O(N log C)$.

Procedăm ca la 'problema $5$':probleme-cu-secvente#prob5 şi căutăm binar valoarea optimă. Şirul va fi transformat în: $b[i] = c[i] - t[i] * X$, $i = 1..N$. Acum trebuie să mai rezolvăm subproblema care cere să determinăm o subsecvenţă de sumă maximă pentru care lungimea se află între $L$ şi $U$. Această subproblemă a fost soluţionată în 'problema anterioară':probleme-cu-secvente#prob9, unde s-a găsit un algoritm liniar. Astfel soluţia acestei probleme are complexitatea $O(N log C)$.

h2(#prob11). Problema 11 ('XorMax':problema/xormax)

Paftenie este un elev eminent. De multe ori îşi pune întrebări care au sau nu răspunsuri. De data aceasta i-a venit o idee nouă. El are un şir de $N$ numere întregi nenegative şi vrea să aleagă o secvenţă a şirului $(a{~i~}, a{~i+1~}, ..., a{~j~})$ astfel încât $a{~i~} xor a{~i+1~} xor ... xor a{~j~}$ să fie maxim ({$1 <= N <= 100 000$}, numerele şirului sunt strict mai mici decât $221$ ).

bq. Se dă un şir de $N$ numere întregi nenegative. Să se aleagă o secvenţă a şirului, $(a{~i~}, a{~i+1~}, ..., a{~j~})$, astfel încât $a{~i~} xor a{~i+1~} xor ... xor a{~j~}$ să fie maxim. Restrictii: $1 <= N <= 100 000$ si $a{~i~} < 221$ cu $i = 1..N$.

h3. Exemplu:

h2(#probp). Probleme propuse

Pentru a vă însuşi mai bine tehnicile învăţate în acest articol, autorul vă sugerează să rezolvaţi următoarele două probleme:

Pentru a vă însuşi mai bine tehnicile învăţate în acest articol, autorul vă sugerează să rezolvaţi următoarele probleme:

* 'Balans':problema/balans
* 'Struţi':problema/struti
* 'Deque':problema/deque

* 'Trie':problema/trie

h2(#bibliografie). Bibliografie