Probleme cu Secvențe

Iulian Oleniuc

💡 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 n0n \ge 0 valori (întregi în cazul nostru) a1,a2,,an\langle a_1, a_2, \ldots, a_n \rangle. Uneori este mai avantajos să le indexăm de la 11, alteori de la 00.

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 bb (de lungime kk) al unui șir aa (de lungime nn) este determinat de o succesiune de indici i1,i2,,ik\langle i_1, i_2, \ldots, i_k \rangle, astfel încât 1i1i2ikn1 \le i_1 \le i_2 \le \cdots \le i_k \le n, și se referă la șirul ai1,ai2,,aik\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 aa se obține eliminând un set de elemente ale lui aa. De exemplu, din șirul 3,1,4,6,1,8\langle 3, \textcolor{lime}{1}, 4, \textcolor{lime}{6}, 1, 8 \rangle putem obține subșirul 3,4,1,8\langle 3, 4, 1, 8 \rangle, eliminând primul element 1\textcolor{lime}{1} și elementul 6\textcolor{lime}{6}.

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

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

Avem și aici o definiție alternativă.

O subsecvență a unui șir aa se obține eliminând din aa un prefix și un sufix (cele două trebuie să fie disjuncte). De exemplu, din șirul 3,1,4,6,1,8\langle \textcolor{lime}{3}, 1, 4, 6, \textcolor{lime}{1}, \textcolor{lime}{8} \rangle putem obține subsecvența 1,4,6\langle 1, 4, 6 \rangle, eliminând prefixul 3\langle \textcolor{lime}{3} \rangle și sufixul 1,8\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 psa[i]\mathrm{ps}_a[i] a ii-a sumă parțială a șirului aa, definiția ne spune că

psa[i]a1+a2++ai.\mathrm{ps}_a[i] \triangleq a_1 + a_2 + \cdots + a_i.

Relația de mai sus este valabilă pentru orice 1in1 \le i \le n, însă este foarte important să nu uităm de cazul de bază psa[0]0\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+1n + 1 sume parțiale ale lui aa pe baza relației

psa[i]={psa[i1]+aidaca˘ i>00daca˘ i=0,\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:

psa[i]a1+a2++ai1psa[i1]+ai.\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 aa de nn elemente și qq întrebări de forma (l,r)(l, r), cu semnificația:

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

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


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

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

suma(l,r)al+al+1++ar=psa[r]psa[l1],\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 1lrn1 \le l \le r \le n.

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

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 O(1)\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 O(n+q)\mathcal{O}(n + q).

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

4 Șmenul lui Mars

Se dau un șir aa de nn elemente, inițial toate nule, și qq operații de forma (l,r,x)(l, r, x), cu semnificația:

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

Să se determine elementele șirului aa la finalul celor qq operații.


Din nou, soluția naivă are complexitatea O(nq)\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)(l, r, x), adunăm valoarea xx la ala_l și o scădem din ar+1a_{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=nr = n. O soluție alternativă ar fi să precedăm această instrucțiune cu un if.

La final, construim în aa șirul psa\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 aa conține numai zerouri. După procesarea ei, obținem

a=0,,0,+xl,0,,0,xr+1,0,,0.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 aa, am obține

psa=0,,0,0+xl,0+x,,0+x,x+xr+1,0,,0,\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ă

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

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


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

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

5 Subsecvența de sumă ss

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

Soluția generală

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

tpsa[r]s.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 aa, 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 ii, fixăm r=ir = i și căutăm în vectorul caracteristic valoarea tt. Dacă am găsit-o, și aceasta ne-a oferit poziția kk, înseamnă că subsecvența (k+1,i)(k + 1, i) are suma elementelor egală cu ss.

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 [106,106][-10^6, 10^6], motiv pentru care a trebuit să shiftez elementele lui left cu 10610^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 O(n)\mathcal{O}(n) memorie suplimentară, deoarece sumele parțiale pot lua doar n+1n + 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 aa sunt numere pozitive, atunci șirul psa\mathrm{ps}_a este crescător, caz în care putem efectua căutare binară pentru găsirea valorii tt în prefixul psa[0],psa[1],,psa[i1]\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 O(nlogn)\mathcal{O}(n \log n), însă rămâne foarte bună.

6 Subsecvența de sumă divizibilă cu nn

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

Soluția este aproape identică cu prima soluție de la problema precedentă, singura diferență fiind că acum lucrăm modulo nn. Mai precis, pentru ca subsecvența (l,r)(l, r) să aibă suma divizibilă cu nn, trebuie ca psa[l1]psa[r](modn)\mathrm{ps}_a[l - 1] \equiv \mathrm{ps}_a[r] \pmod{n}, pentru că, scăzând psa[l1]\mathrm{ps}_a[l - 1] din psa[r]\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 psa\mathrm{ps}_a conține n+1n + 1 elemente, în timp ce numărul de resturi posibile modulo nn este nn. Așadar, conform Principiului lui Dirichlet, există cu siguranță două elemente în psa\mathrm{ps}_a care să obțină același rest la împărțirea la nn. Ei bine, acele două elemente determină subsecvența căutată de noi.

7 Subsecvența de sumă maximă

Se dă un șir aa de lungime nn ș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ă suma(l,r)=ps[r]ps[l1]\operatorname{sum}_a(l, r) = \mathrm{ps}[r] - \mathrm{ps}[l - 1]. Fixăm iarăși capătul-dreapta rr al subsecvenței căutate. Cum dorim să maximizăm valoarea expresiei precedente, în care singura variabilă este ll, deducem că trebuie de fapt să minimizăm valoarea ps[l1]\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 dp[i]\mathrm{dp}[i] am notat suma maximă a unei subsecvențe a lui aa care se termină pe poziția ii:

dp[i]={max(ai,dp[i1]+ai)daca˘ i>00daca˘ i=0.\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 ii, atunci ea fie este ai\langle a_i \rangle, fie este formată dintr-o subsecvență care se termină în i1i - 1 și la finalul căreia se adaugă elementul aia_i. În primul caz, suma subsecvenței este aia_i, iar în cel de-al doilea, suma subsecvenței cu capătul-dreapta în i1i - 1 plus aia_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 kk de sumă maximă

Soluția cu sume parțiale

Putem itera foarte frumos toate cele nk+1n - k + 1 subsecvențe de lungime kk ale lui aa 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.

al,al+1,,arsuma(l,r),ar+1al,al+1,,ar,ar+1suma(l+1,r+1)\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)(l, r) la subsecvența (l+1,r+1)(l + 1, r + 1), pur și simplu ștergem elementul ala_l și îl adăugăm pe ar+1a_{r + 1}. În mod similar putem actualiza și suma.

Mai întâi procesăm subsecvența (1,k)(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ă ss î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 O(n)\mathcal{O}(n)), iar a doua oară cu sume parțiale și căutare binară (memorie suplimentară liniară, însă O(nlogn)\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 ll și rr capetele (practic niște pointeri, de unde și numele metodei) subsecvenței curente. Pornim de la (l,r)=(1,0)(l, r) = (1, 0), adică de la subsecvența de lungime 00 care începe pe poziția 11.

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

  • Dacă x<sx \lt s, incrementăm rr, ca să adăugăm un element nou.
  • Dacă x>sx \gt s, incrementăm ll, 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=nr = n și totuși x<sx \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 ll, fie pe rr, iar cum ambele pot trece prin cel mult nn valori, numărul de pași efectuați nu depășește 2n2 \cdot n. Așadar, complexitatea este O(n)\mathcal{O}(n).

😱 Probleme mai Interesante

10 Suma sumelor elementelor tuturor subsecvențelor

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


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

Ideea constă în a lua fiecare element aia_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)(l, r) conține elementul aia_i dacă și numai dacă 1li1 \le l \le i și irni \le r \le n. Conform regulii produsului, numărul de astfel de subsecvențe este i(ni+1)i \cdot (n - i + 1).

a1,a2,,ai1,aii capete-staˆnga,ai+1,,an1,ana1,a2,,ai1,ai,ai+1,,an1,anni+1 capete-dreapta\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

(i=1naii(ni+1))modm.\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 11 pe poziții consecutive într-un șir binar

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


Faptul că valorile de 11 trebuie să formeze o subsecvență de lungime kk fixă (unde prin kk 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 ll și r=l+k1r = l + k - 1 ale fiecărei subsecvențe posibile, și să calculăm costul necesar aducerii 11-urilor între pozițiile ll și rr.

O parte dintre 11-uri se află deja în subsecvența (l,r)(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 ii-lea 11 din exteriorul subsecvenței pe poziția celui de-al ii-lea 00 din interiorul ei. Evident, este suficient un singur swap pentru a rezolva al ii-lea astfel de 11, deci ksuma(l,r)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 ksuma(l,r)k - \operatorname{sum}_a(l, r).

12 Sume parțiale speciale

Se dă un șir aa de nn elemente. Se dau de asemenea qq întrebări de forma (l,r)(l, r), cu semnificația:

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

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


Să notăm cu suma(l,r)\operatorname{sum}'_a(l, r) suma cerută pe subsecvența (l,r)(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ă

suma(l,r)=ar+ar1++al+2+al+1+al+ar+ar1++al+2+al+1+ar+ar1++al+2+ar+ar1+ar.\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,

suma(l,r)=suma(l,r)+suma(l+1,r)++suma(r,r)=(psa[r]psa[l1])+(psa[r]psa[l])++(psa[r]psa[r1])=(rl+1)psa[r]sumpsa(l1,r1)=(rl+1)psa[r]pspsa[r1]+pspsa[l2].\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 aa. Totodată, trebuie să avem grijă la accesarea poziției l2l - 2 din pspsa\mathrm{ps}_{\mathrm{ps}_a}.

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

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


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

2l3psa[l]=2r3psa[r].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 rr ce îndeplinesc proprietatea dată este egal cu numărul de indici l<rl \lt r ce verifică egalitatea precedent menționată. Evident, vom reține frecvențele valorilor 2l3psa[l]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! 🏆

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