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 valori (întregi în cazul nostru) . Uneori este mai avantajos să le indexăm de la , alteori de la .
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 (de lungime ) al unui șir (de lungime ) este determinat de o succesiune de indici , astfel încât , și se referă la șirul .
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 se obține eliminând un set de elemente ale lui . De exemplu, din șirul putem obține subșirul , eliminând primul element și elementul .
Subsecvența poate fi definită ușor pe baza ideii de subșir.
O subsecvență a unui șir este un subșir al lui cu proprietatea că . Cu alte cuvinte, pozițiile ce-l determină pe sunt consecutive.
Avem și aici o definiție alternativă.
O subsecvență a unui șir se obține eliminând din un prefix și un sufix (cele două trebuie să fie disjuncte). De exemplu, din șirul putem obține subsecvența , eliminând prefixul și sufixul .
Î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 a -a sumă parțială a șirului , definiția ne spune că
Relația de mai sus este valabilă pentru orice , însă este foarte important să nu uităm de cazul de bază , care este vital în problema ce urmează.
Putem calcula foarte ușor și eficient (în timp liniar) toate cele sume parțiale ale lui pe baza relației
justificată astfel:
3
Problema clasică
Se dau un șir de elemente și întrebări de forma , cu semnificația:
Care este suma elementelor subsecvenței din ?
Să se răspundă, pe rând, la fiecare dintre cele întrebări.
Dacă am parcurge fiecare subsecvență în parte, complexitatea algoritmului ar fi , deoarece, în cel mai rău caz, fiecare subsecvență este însăși șirul .
Însă, folosindu-ne de conceptul de sume parțiale, definit mai sus, putem observa că
oricare ar fi .
Așadar, înainte de citirea celor întrebări, precalculăm sumele parțiale ale lui .
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 .
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 .
Întrebare: Ce indexare a vectorilor este mai avantajoasă atunci când lucrăm cu sume parțiale? De la sau de la ?
4
Șmenul lui Mars
Se dau un șir de elemente, inițial toate nule, și operații de forma , cu semnificația:
Fiecare element al subsecvenței crește cu unități.
Să se determine elementele șirului la finalul celor operații.
Din nou, soluția naivă are complexitatea .
Ș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 , adunăm valoarea la și o scădem din .
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
! Vectorula
trebuie să conțină cu un element mai mult decât în mod normal, pentru a nu ieși din el atunci când . O soluție alternativă ar fi să precedăm această instrucțiune cu unif
.
La final, construim în șirul .
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 conține numai zerouri. După procesarea ei, obținem
În acest moment, dacă ar fi să calculăm sumele parțiale ale lui , am obține
adică
Se remarcă ușor că face ce trebuie și pentru .
Complexitatea finală este, evident, .
Întrebare: Cum putem modifica algoritmul pentru a funcționa și în cazul în care nu este inițializat cu zerouri?
5
Subsecvența de sumă
Se dau un șir de elemente și o valoare . Să se determine o subsecvență a lui cu proprietea că suma elementelor sale este egală cu .
Soluția generală
Amintim faptul că . Prin urmare, dacă fixăm capătul-dreapta al subsecvenței căutate, putem deduce ușor ce valoare trebuie să aibă :
Așadar, o soluție în timp liniar pentru problema noastră constă în a calcula sumele parțiale ale lui , 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 , fixăm și căutăm în vectorul caracteristic valoarea . Dacă am găsit-o, și aceasta ne-a oferit poziția , înseamnă că subsecvența are suma elementelor egală cu .
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 , motiv pentru care a trebuit să shiftez elementele lui left
cu 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 memorie suplimentară, deoarece sumele parțiale pot lua doar 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 sunt numere pozitive, atunci șirul este crescător, caz în care putem efectua căutare binară pentru găsirea valorii în prefixul . 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 , însă rămâne foarte bună.
6
Subsecvența de sumă divizibilă cu
De data aceasta, căutăm în șirul o subsecvență de sumă divizibilă cu , unde este chiar numărul de elemente din .
Soluția este aproape identică cu prima soluție de la problema precedentă, singura diferență fiind că acum lucrăm modulo . Mai precis, pentru ca subsecvența să aibă suma divizibilă cu , trebuie ca , pentru că, scăzând din , 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 conține elemente, în timp ce numărul de resturi posibile modulo este . Așadar, conform Principiului lui Dirichlet, există cu siguranță două elemente în care să obțină același rest la împărțirea la . Ei bine, acele două elemente determină subsecvența căutată de noi.
7
Subsecvența de sumă maximă
Se dă un șir de lungime ș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ă . Fixăm iarăși capătul-dreapta al subsecvenței căutate. Cum dorim să maximizăm valoarea expresiei precedente, în care singura variabilă este , deducem că trebuie de fapt să minimizăm valoarea .
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 am notat suma maximă a unei subsecvențe a lui care se termină pe poziția :
Maximul din formulă se traduce astfel: Dacă o subsecvență se termină în , atunci ea fie este , fie este formată dintr-o subsecvență care se termină în și la finalul căreia se adaugă elementul . În primul caz, suma subsecvenței este , iar în cel de-al doilea, suma subsecvenței cu capătul-dreapta în plus .
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 de sumă maximă
Soluția cu sume parțiale
Putem itera foarte frumos toate cele subsecvențe de lungime ale lui 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.
Mai precis, atunci când ne deplasăm de la subsecvența la subsecvența , pur și simplu ștergem elementul și îl adăugăm pe . În mod similar putem actualiza și suma.
Mai întâi procesăm subsecvența .
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ă î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 ), iar a doua oară cu sume parțiale și căutare binară (memorie suplimentară liniară, însă ). Există însă și o soluție liniară și fără memorie auxiliară, oarecum similară cu ideea de Sliding Window.
Menținem în și capetele (practic niște pointeri, de unde și numele metodei) subsecvenței curente. Pornim de la , adică de la subsecvența de lungime care începe pe poziția .
Fie suma curentă. La fiecare pas, extindem subsecvența curentă astfel:
- Dacă , incrementăm , ca să adăugăm un element nou.
- Dacă , incrementăm , 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 și totuși (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 , fie pe , iar cum ambele pot trece prin cel mult valori, numărul de pași efectuați nu depășește . Așadar, complexitatea este .
Probleme mai Interesante
10
Suma sumelor elementelor tuturor subsecvențelor
Se dă un șir de elemente. Pentru fiecare subsecvență posibilă a lui calculăm și adunăm valoarea rezultată la suma totală. Să se afișeze această sumă modulo .
Evident, nu ne permitem să implementăm literalmente procesul descris, deoarece complexitatea necesară ar fi . Avem nevoie de o soluție mai inteligentă, eventual combinatorială.
Ideea constă în a lua fiecare element î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ță conține elementul dacă și numai dacă și . Conform regulii produsului, numărul de astfel de subsecvențe este .
Așadar, soluția constă în calculul expresiei
11
Numărul minim de swap-uri necesare pentru a aduce valorile de pe poziții consecutive într-un șir binar
Se dă un șir de elemente din mulțimea . Se definește operația care interschimbă elementele și . Care este numărul minim de operații ce trebuie efectuate pentru a aduce toate valorile de pe poziții consecutive în șirul ?
Faptul că valorile de trebuie să formeze o subsecvență de lungime fixă (unde prin 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 și ale fiecărei subsecvențe posibile, și să calculăm costul necesar aducerii -urilor între pozițiile și .
O parte dintre -uri se află deja în subsecvența , deci nu trebuie să le mai mutăm. Însă cealaltă parte se află în exteriorul ei. Putem considera, pentru simplitate, că aducem al -lea din exteriorul subsecvenței pe poziția celui de-al -lea din interiorul ei. Evident, este suficient un singur swap pentru a rezolva al -lea astfel de , deci operații în total.
Menținem suma subsecvenței curente folosind Sliding Window, iar pe parcurs calculăm minimul valorilor .
12
Sume parțiale speciale
Se dă un șir de elemente. Se dau de asemenea întrebări de forma , cu semnificația:
Care este valoarea sumei ?
Să se răspundă eficient la cele întrebări.
Să notăm cu suma cerută pe subsecvența . Dacă încercăm să scăpăm de coeficienți și să aranjăm termenii rezultați într-un mod isteț, observăm că
Altfel spus,
Cea mai mișto parte este ultima linie, care ne arată că avem nevoie de sumele parțiale ale sumelor parțiale ale lui . Totodată, trebuie să avem grijă la accesarea poziției din .
13
Numărul de subsecvențe cu de două ori mai mulți de decât de într-un șir binar
Se dă un șir de elemente din mulțimea . Să se determine numărul de subsecvențe ale lui ce conțin de exact două ori mai mulți de decât de .
Numărul de -uri din subsecvența este dat de . Proprietatea din enunț se traduce prin . Altfel spus, . În ideea că vom fixa capătul-dreapta în și vom căuta un adecvat, ne gândim să trecem termenii ce depind de într-o parte, iar pe cei ce depind de în cealaltă, obținând astfel
Prin urmare, numărul subsecvențelor cu capătul-dreapta în ce îndeplinesc proprietatea dată este egal cu numărul de indici ce verifică egalitatea precedent menționată. Evident, vom reține frecvențele valorilor î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.