h1. Probleme cu secvenţe

== include(page="template/implica-te/scrie-articole-2" user_id1="alecman" user_id2="Marius") ==

== include(page="template/implica-te/scrie-articole" user_id="alecman") ==

(Categoria _Algoritmi şi tehnici de programare_, Autor _Cosmin Negruşeri_)

(toc){width: 30em}*{text-align:center} *Conţinut*

(toc){width: 27em}*{text-align:center} *Conţinut*

* 'Introducere ':probleme-cu-secvente#introducere
* 'Problema 1 (Subsecvenţa de sumă maximă) ':probleme-cu-secvente#problema-1
* 'Problema 2 (Maximum Sum) ':probleme-cu-secvente#problema-2

Să vedem ce se întâmplă pe exemplu:

table{width:300px; text-align:right;}.

|_. $a$ | - | $-1$ | $2$ | $3$ | $-2$ | $4$ | $-3$ | $8$ | $-3$ | $1$ |
|_. $sum$ | $0$ | $-1$ | $1$ | $4$ | $2$ | $6$ | $3$ | $11$ | $8$ | $9$ |
şirul e împărţit în trei subsecvenţe $[-1, 2, 3], [-2, 4, -3], [8, -3, 1]$:

table{width:100px; text-align:right;}.

|_. $max$ | $4$ | $6$ | $11$ |
|_. $min$ | $-1$ | $2$ | $8$ |
|_. $best$ | $5$ | $4$ | $8$ |

        int mid = (low + high) / 2;
        build_tree(2 * index, low, mid);
        build_tree(2 * index + 1, mid + 1, high);

        aint[index].maxS = Math.max(aint[2 * index].maxS,
                                    Math.max(aint[2 * index + 1].maxS, aint[2 * index + 1].max - aint[2 * index].min));

        aint[index].maxS = Math.max(aint[2 * index].maxS,
                Math.max(aint[2 * index + 1].maxS, aint[2 * index + 1].max - aint[2 * index].min));

        aint[index].max = Math.max(aint[2 * index].max,aint[2 * index + 1].max);
        aint[index].min = Math.min(aint[2 * index].min,aint[2 * index + 1].min);
    }

    else {
        int mid = (low + high) / 2;
        if (x <= mid && mid < y)

            return  Math.max(queryTree(2 * index, low, mid), queryTree(2 * index + 1, mid + 1, high));

            return Math.max(queryTree(2 * index, low, mid), queryTree(2 * index + 1, mid + 1, high));

        else if (x > mid)
            return queryTree(2 * index + 1, mid + 1, high);
        else

h3. Rezolvare:

Construim întâi şirul sumelor parţiale. Pentru oricare două elemente $sum[i]$ şi $sum[j]$ cu $(i != j)$ modulul sumei unei subsecvenţe din şir va fi $|sum[i] - sum[j]|$. Dacă $i < j$, atunci secvenţa va fi $a[i+1..j]$, iar dacă $j < i$, atunci secvenţa va fi $a[j+1 .. i]$. Astfel, pentru a găsi subsecvenţa de modul minim trebuie, de fapt, să găsim perechea de indici $i$ şi $j$ astfel ca $|sum[i] - sum[j]|$ să fie minim. Sortând şirul sumelor parţiale şi luând o pereche de indici $i < j$, atunci $sum[i] < sum[j]$, iar $|sum[j] - sum[i]| = sum[j] - sum[i]$. Pentru a găsi perechea $(i, j)$ pentru care $i < j$ şi $sum[j] - sum[i]$ este minim, trebuie ca $i$ să fie egal cu $j + 1$. Astfel obţinem un algoritm de complexitate $O(N log N)$.

Construim întâi şirul sumelor parţiale. Pentru oricare două elemente $sum[i]$ şi $sum[j]$ cu $(i != j)$ modulul sumei unei subsecvenţe din şir va fi $|sum[i] - sum[j]|$. Dacă $i < j$, atunci secvenţa va fi $a[i+1..j]$, iar dacă $j < i$, atunci secvenţa va fi $a[j+1 .. i]$. Astfel, pentru a găsi subsecvenţa de modul minim trebuie, de fapt, să găsim perechea de indici $i$ şi $j$ astfel ca $|sum[i] - sum[j]|$ să fie minim. Sortând şirul sumelor parţiale şi luând o pereche de indici $i < j$, atunci $sum[i] < sum[j]$, iar $|sum[j] - sum[i]| = sum[j] - sum[i]$. Pentru a găsi perechea $(i, j)$ pentru care $i < j$ şi $sum[j] - sum[i]$ este minim, trebuie ca $i$ să fie egal cu $j + 1$. Astfel obţinem un algoritm de complexitate $O(N * log N)$.

Să vedem cum merge pe exemplul prezentat:

table{width:300px; text-align:right;}.

|_. $a$ | - | $2$ | $8$ | $-6$ | $-6$ | $9$ | $4$ | $-3$ |
|_. $sum$ | $0$ | $2$ | $10$ | $4$ | $-2$ | $7$ | $11$ | $8$ |
|_. $ind$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ |
În şirul $ind$ vom păstra indicii reali ai sumelor parţiale. După sortare avem:

table{width:300px; text-align:right;}.

|_. $sum$ | $-2$ | $0$ | $2$ | $4$ | $7$ | $8$ | $10$ | $11$ |
|_. $ind$ | $4$ | $0$ | $1$ | $4$ | $5$ | $7$ | $2$ | $6$ |

* Î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~}$.

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(#problema-6). Problema 6 ('Secvenţă':problema/secventa)

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 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_.

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~} &le; i$ şi $a[j{~1~}] &ge; 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.

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ă.

h3. Rezolvare:

Procedăm ca la 'problema $5$':probleme-cu-secvente#problema-5 ş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#problema-9, 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#problema-5 ş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#problema-9, unde s-a găsit un algoritm liniar. Astfel soluţia acestei probleme are complexitatea $O(N * log C)$.

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

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)$.

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)$.

h2(#problema-propuse). Probleme propuse