O secvenţă de modul $2$ ar fi cea reprezentată de sumele $8$ şi $10$, cu indicii $7$ şi $2$. Această secvenţă este $(-6, -6, 9, 4, -3)$. Observăm ca cea mai mică diferenţă între termeni consecutivi e cea dintre $8$ şi $7$, care au indicii $7$ şi $5$, de unde obţinem că subsecvenţa de modul minim este $(4, -3)$.
h2(#prob5). Problema 5 - USACO
h2(#prob5). Problema 5 ( USACO )
Se da un sir $(a{~1~}, a{~2~}, ..., a{~N~})$ format din $N (1 <= N <= 100 000)$ numere intregi ($1 <= a{~i~} <= 2 000$). Se cere sa se determine subsecventa $a[i..i + K - 1]$ cu media aritmetica a elementelor maxima ( $K >= F, 1 <= F <= N$).
Se dă un şir $(a{~1~}, a{~2~}, ..., a{~N~})$ format din $N (1 <= N <= 100 000)$ numere întregi ($1 <= a{~i~} <= 2 000$). Se cere să se determine subsecvenţa $a[i..i + K - 1]$ cu media aritmetică a elementelor maximă ( $K >= F, 1 <= F <= N$).
h4. Exemplu
Pentru sirul $(6, 4, 2, 10, 3, 8, 5, 9, 4, 1)$ si $F = 6$ soluţia optima este $(10, 3, 8, 5, 9, 4)$, cu media $6.5$.
Pentru şirul $(6, 4, 2, 10, 3, 8, 5, 9, 4, 1)$ şi $F = 6$ soluţia optimă este $(10, 3, 8, 5, 9, 4)$, cu media $6.5$.
h3. Rezolvare
Fie $X$ un numar real. Daca obtinem sirul $b$ prin transformarea $b{~i~} = a{~i~} - X$, atunci toate subsecventele sirului $b$ vor avea valoarea mediei elementelor lor cu X mai mica decat valoarea subsecventelor corespunzatoare din sirul $a$. Daca subsecventa de suma maxima din $b$ are valoarea mai mare ca $0$, atunci si media ei va fi mai mare ca $0$. Rezulta astfel ca si media subsecventei corespunzatoare din sirul $a$ va fi mai mare decat $X$, deci media maxima a unei subsecvente din $a$ va fi mai mare ca $X$. Cand subsecventa de suma maxima din sirul $b$ are media mai mica decat zero, atunci orice subsecventa din sirul $a$ va avea media mai mica decat $X$. Iar in cazul in care subsecventa de suma maxima a sirului $b$ are valoarea egala cu zero, atunci subsecventa de medie maxima a sirului $a$ are media $X$. Astfel putem face o cautare binara pentru a determina valoarea $X$ a mediei maxime. Ne mai ramane sa determinam un algoritm eficient pentru gasirea subsecventei de suma maxima de lungime cel putin $F$.
O asemenea solutie este usor de facut urmarind una din ideile din prima problema: fie $best[i]$ subsecventa de suma maxima care se termina in $a[i]$. Evident $best[i] = max(a[i], best[i - 1] + a[i])$. Acum secventa de suma maxima ce se termina in $a[i]$ de lungime cel putin $F$ se gaseste ca $a[i] + a[i - 1] + .. + a[i - F + 2] + best[i - F + 1]$. Aceasta relatie poate fi calculata in $O(1)$ daca ne folosim de trucul sumelor partiale.
Astfel obtinem o solutie de complexitate $O(N log C)$, unde $C$ e valoarea maxima a lui $a{~i~}.
Fie $X$ un număr real. Considerând şirul $b$, obţinut prin transformarea $b{~i~} = a{~i~} - X$, atunci toate subsecvenţele şirului $b$ vor avea valoarea mediei elementelor lor cu $X$ mai mică decât valoarea subsecvenţelor corespunzătoare din şirul $a$. Observăm apariţia a trei cazuri:
* Dacă subsecvenţa de sumă maximă din $b$ are valoarea mai mare ca $0$, atunci şi media ei va fi mai mare ca $0$. Rezultă astfel că şi media subsecvenţei corespunzătoare din şirul $a$ va fi mai mare decât $X$, deci media maximă a unei subsecvenţe din $a$ va fi mai mare ca $X$.
* Cand subsecvenţa de sumă maximă din şirul $b$ are media mai mică decât $0$, atunci orice subsecvenţă din şirul $a$ va avea media mai mică decât $X$.
* În cazul în care subsecvenţa de sumă maximă a şirului $b$ are valoarea egală cu zero, atunci subsecvenţa de medie maximă a şirului $a$ are media $X$.
Astfel putem face o căutare binară pentru a determina valoarea $X$ a mediei maxime. Ne mai rămâne să determinăm un algoritm eficient pentru găsirea subsecvenţei de sumă maximă de lungime cel puţin $F$. O asemenea soluţie urmăreşte una din ideile din prima problemă: fie $best[i]$ subsecvenţa de sumă maximă ce se termină în $a[i]$. Evident $best[i] = max(a[i], best[i - 1] + a[i])$. Acum secvenţa de sumă maximă ce se termină în $a[i]$, de lungime cel puţin $F$ se găseşte ca $a[i] + a[i - 1] + .. + a[i - F + 2] + best[i - F + 1]$. Această relaţie poate fi calculată în $O(1)$ dacă ne folosim de trucul sumelor parţiale. Complexitatea finală este $O(N log C)$, unde $C$ e valoarea maximă a lui $a{~i~}$.
h2(#prob6). Problema 6 ('Secvenţă':problema/secventa)
Gigel are un şir de $N$ numere întregi. Toată lumea ştie că o secvenţă este un subşir de numere care apar pe poziţii consecutive în şirul iniţial. Gigel a definit baza unei secvenţe ca fiind minimul valorilor elementelor din secvenţa respectivă. Fiind dat un număr natural $K$, determinaţi pentru Gigel o secvenţă de lungime cel puţin $K$, cu baza maximă. $( 1 <= K <= N <= 500 000)$
h4. Exemplu
Pentru $K = 3$ şi şirul $(-1, 2, 3, 1, 0, 4, 8, 6)$, secvenţa de bază maximă este $(4, 8, 6)$.
h3. Rezolvare:
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)$.
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 ( *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ă.
Să vedem cum funcţionează rezolvarea pe un exemplu : $a = (-1, 2, 3, 1, 0, 4, 8, 6)$
* inserăm $(-1, 1)$
lista devine: $(-1, 1)$
* inserăm $(2, 2)$
lista devine: $(-1, 1) (2, 2)$
* inserăm $(3, 3)$
lista devine: $(-1, 1) (2, 2) (3, 3)$
elementul minim al secvenţei $a[1..3]$ este $-1$
* inserăm $(1, 4)$
ştergem $(3, 3)$ şi $(2, 2)$
ştergem $(-1, 1)$ ( inserat acum $4$ paşi )
lista de vine: $(1, 4)$
elementul minim al secvenţei $a[2..4]$ este $1$
* inserăm $(0, 5)$
ştergem $(1, 4)$
lista devine: $(0, 5)$
elementul minim al secvenţei $a[3..5]$ este $0$.
* inserăm $(4, 6)$
lista devine: $(0, 5) (4, 6)$
elementul minim al secvenţei $a[4..6]$ este $0$
* inserăm $(8, 7)$
lista devine: $(0, 5) (4, 6) (8, 7)$
elementul minim al secvenţei $a[5..7]$ este $0$
* inserăm $(6, 8)$
ştergem $(8, 7)$
ştergem $(0, 5)$ ( inserat acum $4$ paşi )
lista devine: $(4, 6) (6, 8)$
elementul minim al secvenţei $a[6..8]$ este $4$
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 $NxM (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.
h4. Exemplu
De exemplu pentru $K = 3$ şi matricea <tex>\[ \left( \begin{array}{cccccc}1 & 1 & 3 & 1 & 2 & 7 \\9 & 2 & 3 & 2 & 3 & 2 \\7 & 8 & 2 & 3 & 1 & 5 \\4 & 5 & 6 & 0 & 1 & 4 \end{array} \right)\]</tex>, soluţia optimă va avea $9$ celule.
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^)$.
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.
h4. Exemplu
De exemplu pentru şirul $(0, -6, 2, 1, 4, -1, 3, -5)$ şi $K = 3$, soluţia optimă este $(2, 1, 4, -1, 3)$.
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)$ ).
h2(#prob9). Problema 9 ( _Sum_ - 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)$.
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)$ ) ).
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$. Folosind acea tehnică obţinem o rezolvare de complexitate liniară.
O altă rezolvare frumoasă prezentată în [4] este următoarea: Spunem că o secvenţă este negativă spre stânga dacă suma oricărui prefix ( în afară de secvenţa în sine ) al secvenţei este negativ sau zero. O partiţie a secvenţei $A = (A{~1~},A{~2~},...,A{~k~})$ este minimală negativă spre stânga dacă fiecare $A{~i~}$ este negativă spre stânga, iar suma elementelor lui $A{~i~}$ este strict pozitivă dacă $i != k$. De exemplu secvenţa $(-4, 1, -2, 3)$ este negativă la stânga, pe când secvenţa $(5, -3, 4, -1, 2, -6)$ nu este. Partiţia $(5) (-3, 4) (-1, 2) (-6)$ este minimală negativă la stânga.
Pentru fiecare element din partiţie ţinem minte un pointer $p[i]$ spre ultimul element din subsecvenţa din care face parte. Fiecare interval $(i, p[i])$ va corespunde celei mai scurte subsecvenţe care începe în $i$ şi are suma pozitivă. Pentru a determina o soluţie a problemei pentru fiecare $i$ din care poate începe o subsecvenţă de sumă maximă, ne vom plimba cu un pointer $j$ astfel ca $j$ să fie cât mai depărtat de $i$ şi $j - i + 1 <= U$. Obţinem astfel de fiecare dată o subsecvenţă de sumă maximă ce începe în $i$, cu lungimea mai mică sau egală cu $U$. Indicele $j$ va fi întotdeauna un capăt de secvenţă negativă la stânga şi la fiecare mărire a lui $i$ verificăm dacă lui $j$ îi putem atribui valoarea $p[j+1]$ ( adică dacă $p[j+1] - i + 1 <= U$ ). Dacă secvenţa de sumă maximă de lungime cel mult $U$ ce începe în $i$ are lungimea mai mică decât $L$, atunci secvenţa de sumă maximă cu lungimea cuprinsă între $L$ şi $U$ are lungimea exact $L$ ( complexitate $O(N)$ ).
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)$.
h4. Exemplu
Pentru $L = 1, R = 2$ şi şirurile $c = ( 1, 1, 3, 2, 5 )$ şi $t = ( 4, 2, 5, 3, 6 )$, subsecvenţa cea mai eficientă are costul $0.83$.
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)$.
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$ ).
h4. Exemplu
Pentru şirul $(1, 0, 5, 4, 2)$, secvenţa cu valoarea sumei _xor_ maximă este $(4, 2)$, cu suma $6$.
h3. Rezolvare:
Suma _xor_ a două numere este de fapt adunare binară fără transport, fapt care o face similară operaţiei _modulo_. Problema e asemănătoare cu cea a subsecvenţei de modul maxim. Vom obţine toate sumele _xor_ parţiale şi pentru a vedea pentru $sum[i]$ perechea optimă cu care crează o sumă cât mai mare trebuie să găsim acea sumă $sum[j]$ astfel că fiecare bit al lui $sum[i]$ să fie diferit de fiecare bit al lui $sum[j]$, dacă acest lucru este posibil. Pentru a face această căutare cât mai eficientă, putem menţine sumele $sum[i]$ ca şiruri de caractere $0$ sau $1$ într-un trie [5]. Structura de trie pentru cazul când alfabetul are dimensiunea $2$ este identică cu cea de heap. Această soluţie are complexitatea $O(N log C)$.
