Cuvânt Înainte

În primul rând, trebuie să definim clar câteva noțiuni adesea confundate.

Secvență vs. șir vs. vector

Cuvintele secvență (sequence), șir (string) și vector (array) se referă la exact același lucru — o succesiune de $n \ge 0$ valori (întregi în cazul nostru) $\langle a_1, a_2, \ldots, a_n \rangle$. Uneori este mai avantajos să le indexăm de la $1$, alteori de la $0$.

Subșir vs. subsecvență

În cazul cuvintelor subșir (subsequence) și subsecvență (subarray, contiguous subsequence), situația este mai delicată, mai ales când le amestecăm cu variantele lor din engleză.

Un subșir $b$ (de lungime $k$) al unui șir $a$ (de lungime $n$) este determinat de o succesiune de indici $\langle i_1, i_2, \ldots, i_k \rangle$, astfel încât $1 \le i_1 \le i_2 \le \cdots \le i_k \le n$, și se referă la șirul $\langle a_{i_1}, a_{i_2}, \ldots, a_{i_k} \rangle$.

O definiție alternativă, mai puțin formală, dar și ea regăsită adesea în enunțurile problemelor, este următoarea.

Un subșir al unui șir $a$ se obține eliminând un set de elemente ale lui $a$. De exemplu, din șirul $\langle 3, \textcolor{lime}{1}, 4, \textcolor{lime}{6}, 1, 8 \rangle$ putem obține subșirul $\langle 3, 4, 1, 8 \rangle$, eliminând primul element $\textcolor{lime}{1}$ și elementul $\textcolor{lime}{6}$.

Subsecvența poate fi definită ușor pe baza ideii de subșir.

O subsecvență $b$ a unui șir $a$ este un subșir al lui $a$ cu proprietatea că $i_j + 1 = i_{j + 1}, \forall j \lt k$. Cu alte cuvinte, pozițiile ce-l determină pe $b$ sunt consecutive.

Avem și aici o definiție alternativă.

O subsecvență a unui șir $a$ se obține eliminând din $a$ un prefix și un sufix (cele două trebuie să fie disjuncte). De exemplu, din șirul $\langle \textcolor{lime}{3}, 1, 4, 6, \textcolor{lime}{1}, \textcolor{lime}{8} \rangle$ putem obține subsecvența $\langle 1, 4, 6 \rangle$, eliminând prefixul $\langle \textcolor{lime}{3} \rangle$ și sufixul $\langle \textcolor{lime}{1}, \textcolor{lime}{8} \rangle$.

În limba română, de obicei, cuvântul secvență este folosit cu sensul de subsecvență, însă noi vom folosi al doilea termen pe cât posibil, pentru a reduce riscul de confuzie.

În continuare, vom considera că toate șirurile și subsecvențele cu care vom lucra trebuie să fie nevide.

Probleme de Încălzire

1 Cea mai lungă subsecvență de zerouri

Menținem în length lungimea subsecvenței curente, iar în maxLength și maxRight lungimea unei subsecvențe de lungime maximă și respectiv capătul-dreapta al unei astfel de subsecvențe.

int length = 0;
int maxLength = 0, maxRight;
for (int i = 1; i <= n; i++)
    if (a[i] == 0)
        length++;
    else {
        if (length > maxLength) {
            maxLength = length;
            maxRight = i - 1;
        }
        length = 0;
    }

Trebuie să avem grijă la cazul în care subsecvența maximală se termină pe ultima poziție. În acest sens, trebuie să facem o eventuală actualizare a variabilelor maxLength și maxRight inclusiv la finalul for-ului.

if (length > maxLength) {
    maxLength = length;
    maxRight = n;
}

Din lungime și capătul-dreapta putem deduce capătul-stânga al subsecvenței.

const int maxLeft = maxRight - maxLength + 1;
cout << maxLeft << ' ' << maxRight << '\n';

Întrebare: Cum putem evita duplicarea codului care actualizează răspunsul? Se merită?

2 Cea mai lungă subsecvență de elemente egale

Codul este aproape același. Se schimbă doar vreo doi indici, căci acum nu ne mai uităm la elemente individuale, ci la perechi de elemente situate pe poziții consecutive.

int length = 1;
int maxLength = 0, maxRight;
for (int i = 2; i <= n; i++)
    if (a[i] == a[i - 1])
        length++;
    else {
        if (length > maxLength) {
            maxLength = length;
            maxRight = i - 1;
        }
        length = 1;
    }
if (length > maxLength) {
    maxLength = length;
    maxRight = n;
}

Întrebare: Cum putem reduce această problemă la problema precedentă? Cu alte cuvinte, dacă avem un input pentru problema curentă și o funcție care o rezolvă pe cea precedentă, cum putem apela (și eventual prelucra rezultatul returnat de) acea funcție în așa fel încât să obținem un răspuns pentru problema dată?

Sume Parțiale

O sumă parțială a unui șir reprezintă suma elementelor unui prefix al acelui șir. De exemplu, dacă notăm cu $\mathrm{ps}_a[i]$ a $i$-a sumă parțială a șirului $a$, definiția ne spune că

$$\mathrm{ps}_a[i] \triangleq a_1 + a_2 + \cdots + a_i.$$

Relația de mai sus este valabilă pentru orice $1 \le i \le n$, însă este foarte important să nu uităm de cazul de bază $\mathrm{ps}_a[0] \triangleq 0$, care este vital în problema ce urmează.

Putem calcula foarte ușor și eficient (în timp liniar) toate cele $n + 1$ sume parțiale ale lui $a$ pe baza relației

$$\mathrm{ps}_a[i] = \begin{cases} \mathrm{ps}_a[i - 1] + a_i & \text{dacă } i \gt 0\\ 0 & \text{dacă } i = 0 \end{cases},$$

justificată astfel:

$$\mathrm{ps}_a[i] \triangleq \underbrace{a_1 + a_2 + \cdots + a_{i - 1}}_{\mathrm{ps}_a[i - 1]} + a_i.$$

3 Problema clasică

Se dau un șir $a$ de $n$ elemente și $q$ întrebări de forma $(l, r)$, cu semnificația:

Care este suma elementelor subsecvenței $\langle a_l, a_{l + 1}, \ldots, a_r \rangle$ din $a$?

Să se răspundă, pe rând, la fiecare dintre cele $q$ întrebări.

Dacă am parcurge fiecare subsecvență în parte, complexitatea algoritmului ar fi $\mathcal{O}(n \cdot q)$, deoarece, în cel mai rău caz, fiecare subsecvență este însăși șirul $a$.

Însă, folosindu-ne de conceptul de sume parțiale, definit mai sus, putem observa că

$$\operatorname{sum}_a(l, r) \triangleq a_l + a_{l + 1} + \cdots + a_r = \mathrm{ps}_a[r] - \mathrm{ps}_a[l - 1],$$

oricare ar fi $1 \le l \le r \le n$.

Așadar, înainte de citirea celor $q$ întrebări, precalculăm sumele parțiale ale lui $a$.

vector<int> ps(n + 1);
ps[0] = 0; // ps[0] era oricum 0, însă am lăsat linia pentru claritate
for (int i = 1; i <= n; i++)
    ps[i] = ps[i - 1] + a[i];

După aceea, citim fiecare întrebare și răspundem la ea în $\mathcal{O}(1)$.

int q; cin >> q;
for (int i = 0; i < q; i++) {
    int l, r; cin >> l >> r;
    cout << ps[r] - ps[l - 1] << '\n';
}

Complexitatea finală a algoritmului este $\mathcal{O}(n + q)$.

Întrebare: Ce indexare a vectorilor este mai avantajoasă atunci când lucrăm cu sume parțiale? De la $0$ sau de la $1$?

4 Șmenul lui Mars

Se dau un șir $a$ de $n$ elemente, inițial toate nule, și $q$ operații de forma $(l, r, x)$, cu semnificația:

Fiecare element al subsecvenței $\langle a_l, a_{l + 1}, \ldots, a_r \rangle$ crește cu $x$ unități.

Să se determine elementele șirului $a$ la finalul celor $q$ operații.

Din nou, soluția naivă are complexitatea $\mathcal{O}(n \cdot q)$.

Șmenul lui Mars (tehnică ce poartă numele de Difference Arrays în limba engleză) se bazează pe faptul că nu este nevoie să efectuăm fiecare operație în parte (cel puțin nu în întregime), ci le putem procesa pe toate simultan, la final.

Pentru fiecare operație $(l, r, x)$, adunăm valoarea $x$ la $a_l$ și o scădem din $a_{r + 1}$.

int q; cin >> q;
for (int i = 0; i < q; i++) {
    int l, r, x; cin >> l >> r >> x;
    a[l] += x;
    a[r + 1] -= x;
}

Atenție la instrucțiunea a[r + 1] -= x! Vectorul a trebuie să conțină cu un element mai mult decât în mod normal, pentru a nu ieși din el atunci când $r = n$. O soluție alternativă ar fi să precedăm această instrucțiune cu un if.

La final, construim în $a$ șirul $\mathrm{ps}_a$.

for (int i = 2; i <= n; i++)
    a[i] += a[i - 1];

Pentru a înțelege de ce funcționează șmenul, vom analiza doar prima operație, adică cea care se efectuează când $a$ conține numai zerouri. După procesarea ei, obținem

$$a = \langle 0, \ldots, 0, \underbrace{+x}_{l}, 0, \ldots, 0, \underbrace{-x}_{r + 1}, 0, \ldots, 0 \rangle.$$

În acest moment, dacă ar fi să calculăm sumele parțiale ale lui $a$, am obține

$$\mathrm{ps}_a = \langle 0, \ldots, 0, \underbrace{0 + x}_{l}, 0 + x, \ldots, 0 + x, \underbrace{-x + x}_{r + 1}, 0, \ldots, 0 \rangle,$$

adică

$$\mathrm{ps}_a = \langle 0, \ldots, 0, \underbrace{x}_{l}, \ldots, \underbrace{x}_{r}, 0, \ldots, 0 \rangle.$$

Se remarcă ușor că $\mathrm{ps}_a$ face ce trebuie și pentru $q \gt 1$.

Complexitatea finală este, evident, $\mathcal{O}(n + q)$.

Întrebare: Cum putem modifica algoritmul pentru a funcționa și în cazul în care $a$ nu este inițializat cu zerouri?

5 Subsecvența de sumă $s$

Se dau un șir $a$ de $n$ elemente și o valoare $s$. Să se determine o subsecvență a lui $a$ cu proprietea că suma elementelor sale este egală cu $s$.

Soluția generală

Amintim faptul că $\operatorname{sum}_a(l, r) = \mathrm{ps}_a[r] - \mathrm{ps}_a[l - 1]$. Prin urmare, dacă fixăm capătul-dreapta $r$ al subsecvenței căutate, putem deduce ușor ce valoare trebuie să aibă $\mathrm{ps}_a[l - 1]$:

$$t \triangleq \mathrm{ps}_a[r] - s.$$

Așadar, o soluție în timp liniar pentru problema noastră constă în a calcula sumele parțiale ale lui $a$, reținând pe parcurs într-un vector caracteristic (sau chiar map ori unordered_map) sumele parțiale de până la pasul curent, împreună cu indicii corespunzători.

Pentru fiecare pas $i$, fixăm $r = i$ și căutăm în vectorul caracteristic valoarea $t$. Dacă am găsit-o, și aceasta ne-a oferit poziția $k$, înseamnă că subsecvența $(k + 1, i)$ are suma elementelor egală cu $s$.

int l = -1, r = -1;
vector<int> left(2e6 + 1, -1);
int ps = 0;
for (int i = 1; i <= n; i++) {
    left[1e6 + ps] = i - 1;
    ps += a[i];
    const int t = ps - s;
    if (left[1e6 + t] != -1) {
        l = left[1e6 + t] + 1;
        r = i;
        break;
    }
}
cout << l << ' ' << r << '\n';

Am considerat că sumele parțiale nu ies din intervalul $[-10^6, 10^6]$, motiv pentru care a trebuit să shiftez elementele lui left cu $10^6$ poziții la dreapta.

Iată și soluția ce folosește unordered_map pentru vectorul left. Aceasta este mai clară și, în plus, se pretează mai bine pentru cazul în care sumele parțiale au valori potențiale foarte mari. Un alt avantaj al acestei soluții este că folosește doar $\mathcal{O}(n)$ memorie suplimentară, deoarece sumele parțiale pot lua doar $n + 1$ valori, cel mult.

int l = -1, r = -1;
unordered_map<int, int> left;
int ps = 0;
for (int i = 1; i <= n; i++) {
    left[ps] = i - 1;
    ps += a[i];
    const int t = ps - s;
    if (left.count(t)) {
        l = left[t] + 1;
        r = i;
        break;
    }
}
cout << l << ' ' << r << '\n';

Soluția pentru numere pozitive

Observăm că dacă elementele lui $a$ sunt numere pozitive, atunci șirul $\mathrm{ps}_a$ este crescător, caz în care putem efectua căutare binară pentru găsirea valorii $t$ în prefixul $\langle \mathrm{ps}_a[0], \mathrm{ps}_a[1], \ldots, \mathrm{ps}_a[i - 1] \rangle$. Astfel, scăpăm de nevoia de vector caracteristic.

int l = -1, r = -1;
for (int i = 1; i <= n; i++) {
    const int t = ps[i] - s;
    const int k = lower_bound(ps.begin(), ps.begin() + i, t) - ps.begin();
    if (k < i && ps[k] == t) {
        l = k + 1;
        r = i;
        break;
    }
}
cout << l << ' ' << r << '\n';

Complexitatea crește la $\mathcal{O}(n \log n)$, însă rămâne foarte bună.

6 Subsecvența de sumă divizibilă cu $n$

De data aceasta, căutăm în șirul $a$ o subsecvență de sumă divizibilă cu $n$, unde $n$ este chiar numărul de elemente din $a$.

Soluția este aproape identică cu prima soluție de la problema precedentă, singura diferență fiind că acum lucrăm modulo $n$. Mai precis, pentru ca subsecvența $(l, r)$ să aibă suma divizibilă cu $n$, trebuie ca $\mathrm{ps}_a[l - 1] \equiv \mathrm{ps}_a[r] \pmod{n}$, pentru că, scăzând $\mathrm{ps}_a[l - 1]$ din $\mathrm{ps}_a[r]$, restul comun se va anula.

int l = -1, r = -1;
vector<int> left(n, -1);
int ps = 0;
for (int i = 1; i <= n; i++) {
    left[ps % n] = i - 1;
    ps += a[i];
    if (left[ps % n] != -1) {
        l = left[ps % n] + 1;
        r = i;
        break;
    }
}
cout << l << ' ' << r << '\n';

Mai interesantă este argumentarea faptului că problema admite soluție întotdeauna. Ei bine, șirul $\mathrm{ps}_a$ conține $n + 1$ elemente, în timp ce numărul de resturi posibile modulo $n$ este $n$. Așadar, conform Principiului lui Dirichlet, există cu siguranță două elemente în $\mathrm{ps}_a$ care să obțină același rest la împărțirea la $n$. Ei bine, acele două elemente determină subsecvența căutată de noi.

7 Subsecvența de sumă maximă

Se dă un șir $a$ de lungime $n$ și ni se cere să determinăm o subsecvență cu suma elementelor maximă.

Soluția cu sume parțiale

Prima soluție se bazează pe deja bine-cunoscutul fapt că $\operatorname{sum}_a(l, r) = \mathrm{ps}[r] - \mathrm{ps}[l - 1]$. Fixăm iarăși capătul-dreapta $r$ al subsecvenței căutate. Cum dorim să maximizăm valoarea expresiei precedente, în care singura variabilă este $l$, deducem că trebuie de fapt să minimizăm valoarea $\mathrm{ps}[l - 1]$.

Așadar, menținem suma parțială minimă minPS de până la pasul curent, împreună cu indicele minL unde a fost obținută, și actualizăm corespunzător soluția după fiecare pas.

int maxS = -1e9, maxL = -1, maxR = -1;
int ps = 0, minPS = 1e9, minL = -1;
for (int i = 1; i <= n; i++) {
    if (ps < minPS) {
        minPS = ps;
        minL = i;
    }
    ps += a[i];
    const int s = ps - minPS;
    if (s > maxS) {
        maxS = s;
        maxL = minL;
        maxR = i;
    }
}
cout << maxL << ' ' << maxR << '\n';

Soluția cu programare dinamică

Această soluție folosește recurența următoare, unde prin $\mathrm{dp}[i]$ am notat suma maximă a unei subsecvențe a lui $a$ care se termină pe poziția $i$:

$$\mathrm{dp}[i] = \begin{cases} \max(a_i, \mathrm{dp}[i - 1] + a_i) & \text{dacă } i \gt 0\\ 0 & \text{dacă } i = 0 \end{cases}.$$

Maximul din formulă se traduce astfel: Dacă o subsecvență se termină în $i$, atunci ea fie este $\langle a_i \rangle$, fie este formată dintr-o subsecvență care se termină în $i - 1$ și la finalul căreia se adaugă elementul $a_i$. În primul caz, suma subsecvenței este $a_i$, iar în cel de-al doilea, suma subsecvenței cu capătul-dreapta în $i - 1$ plus $a_i$.

Nu este nevoie să stocăm întregul vector dp, ci doar ultima valoare a sa, căci doar de ea depinde valoarea curentă. Reținem pe parcurs maximul acestei valori, precum și indicii corespunzători.

int maxDP = -1e9, maxL = -1, maxR = -1;
int dp = 0, l = -1;
for (int i = 1; i <= n; i++) {
    if (dp > 0)
        dp += a[i];
    else {
        dp = a[i];
        l = i;
    }
    if (dp > maxDP) {
        maxDP = dp;
        maxL = l;
        maxR = i;
    }
}
cout << maxL << ' ' << maxR << '\n';

Sliding Window

8 Subsecvența de lungime $k$ de sumă maximă

Soluția cu sume parțiale

Putem itera foarte frumos toate cele $n - k + 1$ subsecvențe de lungime $k$ ale lui $a$ astfel:

for (int l = 1, r = k; r <= n; l++, r++)

Calculăm suma fiecărei subsecvențe și actualizăm maximul. O primă idee este să folosim sume parțiale, ca mai jos.

int maxS = -1e9, maxL = -1;
for (int l = 1, r = k; r <= n; l++, r++) {
    const int s = ps[r] - ps[l - 1];
    if (s > maxS) {
        maxS = s;
        maxL = l;
    }
}
const int maxR = maxL + k - 1;
cout << maxL << ' ' << maxR << '\n';

Soluția cu Sliding Window

Putem scăpa de sumele parțiale, și implicit de nevoia de vector auxiliar, observând că subsecvența curentă se schimbă foarte puțin de la un pas la altul, același lucru fiind valabil deci și pentru suma sa.

$$\begin{gather*} \overbrace{a_l, a_{l + 1}, \ldots, a_r}^{\operatorname{sum}_a(l, r)}, a_{r + 1}\\ a_l, \underbrace{a_{l + 1}, \ldots, a_r, a_{r + 1}}_{\operatorname{sum}_a(l + 1, r + 1)} \end{gather*}$$

Mai precis, atunci când ne deplasăm de la subsecvența $(l, r)$ la subsecvența $(l + 1, r + 1)$, pur și simplu ștergem elementul $a_l$ și îl adăugăm pe $a_{r + 1}$. În mod similar putem actualiza și suma.

Mai întâi procesăm subsecvența $(1, k)$.

int s = 0;
for (int i = 1; i <= k; i++)
    s += a[i];
int maxS = s, maxL = 1;

Iar apoi le procesăm și pe celelalte, menținând în s suma curentă.

for (int l = 2, r = k + 1; r <= n; l++, r++) {
    s += a[r] - a[l - 1];
    if (s > maxS) {
        maxS = s;
        maxL = l;
    }
}
const int maxR = maxL + k - 1;
cout << maxL << ' ' << maxR << '\n';

Two Pointers

9 Subsecvența de sumă $s$ într-un șir de numere pozitive

Deja am rezolvat problema asta de două ori. Prima oară cu vector caracteristic (deci relativ multă memorie suplimentară, dar $\mathcal{O}(n)$), iar a doua oară cu sume parțiale și căutare binară (memorie suplimentară liniară, însă $\mathcal{O}(n \log n)$). Există însă și o soluție liniară și fără memorie auxiliară, oarecum similară cu ideea de Sliding Window.

Menținem în $l$ și $r$ capetele (practic niște pointeri, de unde și numele metodei) subsecvenței curente. Pornim de la $(l, r) = (1, 0)$, adică de la subsecvența de lungime $0$ care începe pe poziția $1$.

Fie $x$ suma curentă. La fiecare pas, extindem subsecvența curentă astfel:

• Dacă $x \lt s$, incrementăm $r$, ca să adăugăm un element nou.
• Dacă $x \gt s$, incrementăm $l$, ca să renunțăm la un element.

Facem asta până când dăm de subsecvența căutată, sau până când $r = n$ și totuși $x \lt s$ (caz în care am vrea să adăugăm un element pentru a mări suma, dar nu avem de unde, deci concluzionăm că nu există soluție).

int l = 1, r = 0, x = 0;
while (x != s) {
    if (x < s) {
        if (r == n) {
            l = -1;
            r = -1;
            break;
        }
        x += a[++r];
    }
    if (x > s)
        x -= a[l++];
}
cout << l << ' ' << r << '\n';

La fiecare pas incrementăm fie pe $l$, fie pe $r$, iar cum ambele pot trece prin cel mult $n$ valori, numărul de pași efectuați nu depășește $2 \cdot n$. Așadar, complexitatea este $\mathcal{O}(n)$.

Probleme mai Interesante

10 Suma sumelor elementelor tuturor subsecvențelor

Se dă un șir $a$ de $n$ elemente. Pentru fiecare subsecvență $(l, r)$ posibilă a lui $a$ calculăm $\operatorname{sum}_a(l, r)$ și adunăm valoarea rezultată la suma totală. Să se afișeze această sumă modulo $\mathfrak{m} \triangleq 10^9 + 7$.

Evident, nu ne permitem să implementăm literalmente procesul descris, deoarece complexitatea necesară ar fi $\mathcal{O}(n^2)$. Avem nevoie de o soluție mai inteligentă, eventual combinatorială.

Ideea constă în a lua fiecare element $a_i$ în parte și a calcula din câte subsecvențe face parte. După aceea, nu avem decât să-l înmulțim cu valoarea respectivă și să-l adunăm la suma totală.

Putem determina acea valoare în timp constant? Da! O subsecvență $(l, r)$ conține elementul $a_i$ dacă și numai dacă $1 \le l \le i$ și $i \le r \le n$. Conform regulii produsului, numărul de astfel de subsecvențe este $i \cdot (n - i + 1)$.

$$\begin{gather*} \overbrace{a_1, a_2, \ldots, a_{i - 1}, a_i}^{i \text{ capete-stânga}}, a_{i + 1}, \ldots, a_{n - 1}, a_n\\ a_1, a_2, \ldots, a_{i - 1}, \underbrace{a_i, a_{i + 1}, \ldots, a_{n - 1}, a_n}_{n - i + 1 \text{ capete-dreapta}} \end{gather*}$$

Așadar, soluția constă în calculul expresiei

$$\left( \sum_{i = 1}^n a_i \cdot i \cdot (n - i + 1) \right) \operatorname{mod} \mathfrak{m}.$$

11 Numărul minim de swap-uri necesare pentru a aduce valorile de $1$ pe poziții consecutive într-un șir binar

Se dă un șir $a$ de $n$ elemente din mulțimea $\{0, 1\}$. Se definește operația $\operatorname{swap}_a(i, j)$ care interschimbă elementele $a_i$ și $a_j$. Care este numărul minim de operații $\operatorname{swap}_a$ ce trebuie efectuate pentru a aduce toate valorile de $1$ pe poziții consecutive în șirul $a$?

Faptul că valorile de $1$ trebuie să formeze o subsecvență de lungime $k$ fixă (unde prin $k$ notăm numărul lor) ne duce cu gândul la ideea de Sliding Window. În consecință, ne gândim să fixăm, pe rând, capetele $l$ și $r = l + k - 1$ ale fiecărei subsecvențe posibile, și să calculăm costul necesar aducerii $1$-urilor între pozițiile $l$ și $r$.

O parte dintre $1$-uri se află deja în subsecvența $(l, r)$, deci nu trebuie să le mai mutăm. Însă cealaltă parte se află în exteriorul ei. Putem considera, pentru simplitate, că aducem al $i$-lea $1$ din exteriorul subsecvenței pe poziția celui de-al $i$-lea $0$ din interiorul ei. Evident, este suficient un singur swap pentru a rezolva al $i$-lea astfel de $1$, deci $k - \operatorname{sum}_a(l, r)$ operații în total.

Menținem suma subsecvenței curente folosind Sliding Window, iar pe parcurs calculăm minimul valorilor $k - \operatorname{sum}_a(l, r)$.

12 Sume parțiale speciale

Se dă un șir $a$ de $n$ elemente. Se dau de asemenea $q$ întrebări de forma $(l, r)$, cu semnificația:

Care este valoarea sumei $1 \cdot a_l + 2 \cdot a_{l + 1} + \cdots + (r - l + 1) \cdot a_r$?

Să se răspundă eficient la cele $q$ întrebări.

Să notăm cu $\operatorname{sum}'_a(l, r)$ suma cerută pe subsecvența $(l, r)$. Dacă încercăm să scăpăm de coeficienți și să aranjăm termenii rezultați într-un mod isteț, observăm că

$$\begin{align*} \operatorname{sum}'_a(l, r) &= a_r + a_{r - 1} + \cdots + a_{l + 2} + a_{l + 1} + a_l\\ &+ a_r + a_{r - 1} + \cdots + a_{l + 2} + a_{l + 1}\\ &+ a_r + a_{r - 1} + \cdots + a_{l + 2}\\ &\,\,\,\vdots\\ &+ a_r + a_{r - 1}\\ &+ a_r. \end{align*}$$

Altfel spus,

$$\begin{align*} \operatorname{sum}'_a(l, r) &= \operatorname{sum}_a(l, r) + \operatorname{sum}_a(l + 1, r) + \cdots + \operatorname{sum}_a(r, r)\\ &= (\mathrm{ps}_a[r] - \mathrm{ps}_a[l - 1]) + (\mathrm{ps}_a[r] - \mathrm{ps}_a[l]) + \cdots + (\mathrm{ps}_a[r] - \mathrm{ps}_a[r - 1])\\ &= (r - l + 1) \cdot \mathrm{ps}_a[r] - \operatorname{sum}_{\mathrm{ps}_a}(l - 1, r - 1)\\ &= (r - l + 1) \cdot \mathrm{ps}_a[r] - \mathrm{ps}_{\mathrm{ps}_a}[r - 1] + \mathrm{ps}_{\mathrm{ps}_a}[l - 2]. \end{align*}$$

Cea mai mișto parte este ultima linie, care ne arată că avem nevoie de sumele parțiale ale sumelor parțiale ale lui $a$. Totodată, trebuie să avem grijă la accesarea poziției $l - 2$ din $\mathrm{ps}_{\mathrm{ps}_a}$.

13 Numărul de subsecvențe cu de două ori mai mulți de $1$ decât de $0$ într-un șir binar

Se dă un șir $a$ de $n$ elemente din mulțimea $\{0, 1\}$. Să se determine numărul de subsecvențe ale lui $a$ ce conțin de exact două ori mai mulți de $1$ decât de $0$.

Numărul de $1$-uri din subsecvența $(l + 1, r)$ este dat de $\operatorname{sum}_a(l + 1, r)$. Proprietatea din enunț se traduce prin $\operatorname{sum}_a(l + 1, r) = 2 / 3 \cdot (r - l)$. Altfel spus, $3 \cdot (\mathrm{ps}_a[r] - \mathrm{ps}_a[l]) = 2 \cdot (r - l)$. În ideea că vom fixa capătul-dreapta în $r$ și vom căuta un $l$ adecvat, ne gândim să trecem termenii ce depind de $r$ într-o parte, iar pe cei ce depind de $l$ în cealaltă, obținând astfel

$$2 \cdot l - 3 \cdot \mathrm{ps}_a[l] = 2 \cdot r - 3 \cdot \mathrm{ps}_a[r].$$

Prin urmare, numărul subsecvențelor cu capătul-dreapta în $r$ ce îndeplinesc proprietatea dată este egal cu numărul de indici $l \lt r$ ce verifică egalitatea precedent menționată. Evident, vom reține frecvențele valorilor $2 \cdot l - 3 \cdot \mathrm{ps}_a[l]$ într-un vector de frecvență construit pe parcurs.

Probleme pentru Acasă

În general, problemele de mai jos sunt instanțe, uneori puțin particularizate, ale problemelor discutate în cursul de astăzi. Nu toate problemele din curs se regăsesc pe listă, și nici vice-versa. De asemenea, problemele nu sunt ordonate în vreun fel, însă dificultatea lor variază. Prin urmare, se recomandă rezolvarea a cât mai multe!

• secvzero
• secvegale
• sumainsecv
• secv011
• secvsummax
• swap01
• easysum
• secvk
• mars
• qtsume
• secvdesumas
• nrsecvente
• secvegale2
• sumesecv1

Articole Utile

Întâmplarea face că am scris, de-a lungul timpului, articole despre patru dintre tehnicile abordate în acest curs. Acestea explorează aplicații mai avansate ale lor, dar oarecum îndepărtate de ideea de probleme cu subsecvențe, motiv pentru care nici nu au fost incluse în curs. În orice caz, consider că articolele acestea pot fi o lectură utilă, mai ales pentru ONI.

• Sume parțiale
• Șmenul lui Mars
• Two Pointers
• Subsecvența de sumă maximă