Tehnica Two-Pointers în C++

Tehnica Two-Pointers în C++

Two-Pointers este o tehnică folosită adesea în concursurile de informatică, dar mai cu seamă în problemele de la interviurile de angajare. Ea nu este un algoritm concret – nici măcar un șablon –, ci mai degrabă o filosofie. Aceasta ne spune că putem optimiza diverse probleme de parcurgere a vectorilor folosind doi pointeri ll (left) și rr (right), pe care la fiecare pas să-i incrementăm sau decrementăm, după caz. În acest articol vom rezolva șapte probleme interesante, care în total explorează trei moduri diferite de a aplica tehnica Two-Pointers.

Problema 1.

Se dă un vector vv indexat de la 11 format din nn numere naturale nenule. Să se determine capetele unei subsecvențe a lui vv ce are suma elementelor egală cu kk Dacă nu există soluție, se va returna perechea (0,0)(0, 0) De exemplu, pentru v=6,1,8,3,1,4v = \langle 6, 1, 8, 3, 1, 4 \rangle și k=12k = 12 un răspuns posibil este (2,4)(2, 4) (link)

Soluția naivă presupune să explorăm în mod explicit fiecare subsecvență posibilă. Această idee poate fi implementată în două moduri, ambele conducând însă la algoritmi ineficienți. Prima variantă este să ne fixăm cu două for-uri indicii ll și rr ai subsecvenței curente, și să mai luăm un for pentru a calcula suma elementelor acesteia. Complexitate O(n3)O(n^3)

for (int l = 1; l <= n; l++)
for (int r = l; r <= n; r++) {
int s = 0;
for (int i = l; i <= r; i++)
s += v[i];
if (s == k)
return make_pair(l, r);
}
return make_pair(0, 0);

Cealaltă variantă se obține observând că al treilea for din algoritmul de mai sus este redundant. Nu are sens să recalculăm suma pentru fiecare pereche (l,r)(l, r) Pentru un ll fixat, știm că suma elementelor până la rr este egală cu suma elementelor până la r1r - 1 plus v[r]v[r] Așadar, putem actualiza suma curentă ss pe parcursul celui de-al doilea for. Noua complexitate este O(n2)O(n^2)

for (int l = 1; l <= n; l++) {
int s = 0;
for (int r = l; r <= n; r++) {
s += v[r];
if (s == k)
return make_pair(l, r);
}
}
return make_pair(0, 0);

Soluția în O(n)O(n)

Totuși, încă se efectuează o grămadă de iterații inutile. Observăm că, dacă subsecvența curentă [l,r][l, r] are suma elementelor mai mare decât kk atunci nu mai are rost să-l incrementăm pe rr Este clar că toate subsecvențele [l,r][l, r'] cu r>rr' \gt r vor avea și ele suma mai mare decât kk

Asta pentru că elementele vectorului sunt pozitive – altfel, ideea n-ar mai fi funcționat. Să luăm drept exemplu v=3,5,4,2v = \langle 3, 5, -4, 2 \rangle și k=6k = 6 De acum încolo, vom nota cu s(l,r)s(l, r) suma elementelor din subsecvența [l,r][l, r] Avem s(1,2)=8>6s(1, 2) = 8 \gt 6 și s(1,4)=6s(1, 4) = 6 Dacă pentru l=1l = 1 ne-am opri cu rr în 22 am rata soluția (1,4)(1, 4) care este și unică.

Deci, când suma curentă îl depășește pe kk ne oprim din a-l incrementa pe rr și trecem la următorul ll Iar aici intervine observația cheie. După ce îl incrementăm pe ll are sens să-l resetăm complet pe rr sau îl putem lăsa așa și eventual să-i adăugăm un ±1\pm 1

 v[l1] v[l] v[l+1]  v[r1]<k v[r]>k v[r+1] \cdots \text{ } v[l - 1] \text{ } \overbrace{\underbrace{v[l] \text{ } v[l + 1] \text{ } \cdots \text{ } v[r - 1]}_{\lt k} \text{ } v[r]}^{\gt k} \text{ } v[r + 1] \text{ } \cdots

Răspunsul este că da, îl putem lăsa pe rr exact așa cum este. Se vede clar din schema de mai sus că, pentru capătul din stânga fixat în l+1l + 1 cel din dreapta nu are rost să fie mai mic decât rr Am obține o sumă mai mică decât s(l,r1)s(l, r - 1) care deja este mai mică decât kk

Two-Pointers in effect

Și iată că am ajuns la formularea clasică a șmenului:

Inițializăm suma curentă ss cu 00 Pornim cu l=1l = 1 și r=0r = 0 marcând că începem cu subsecvența vidă ce începe în 11 La fiecare pas, comparăm ss cu kk Dacă s=ks = k returnăm perechea (l,r)(l, r) Altfel, dacă s<ks \lt k îl incrementăm pe rr iar dacă s>ks \gt k îl incrementăm pe ll

Să analizăm puțin și complexitatea algoritmului. Cel mai nefavorabil caz este cel în care nu avem soluție, pentru că parcurgem tot vectorul. Mai exact, ne oprim abia după ce r>nr \gt n La fiecare pas, incrementăm exact una dintre variabilele ll și rr Prin urmare, numărul maxim de iterații efectuate este 2n2n Pointer-ul rr ia pe rând toate valorile de la 11 la nn iar ll pornește din 11 și crește din 11 în 11 până ne oprim, atingând în cel mai rău caz valoarea nn Așadar, algoritmul este liniar, având complexitatea O(n)O(n)

int l = 1, r = 0, s = 0;
while (s != k) {
if (s < k) {
if (r == n)
return make_pair(0, 0);
s += v[++r];
}
if (s > k)
s -= v[l++];
}
return make_pair(l, r);

Iată și o implementare ușor mai clară, care scapă de if-ul ăla enervant. Îl iterăm frumos pe rr de la 11 la nn iar la fiecare pas îl ajustăm pe ll incrementându-l cât este nevoie.

int l = 1, s = 0;
for (int r = 1; r <= n; r++) {
s += v[r];
while (s > k)
s -= v[l++];
if (s == k)
return make_pair(l, r);
}
return make_pair(0, 0);

Nu în ultimul rând, am pregătit mai jos o animație care ar trebui să clarifice totul

Vă recomand să rezolvați și extinderea la 2D a problemei. Ideea este să comprimăm coloanele matricei, cum am explicat și aici.

Dacă aveam și numere negative

După cum spuneam, soluția asta merge doar pe numere pozitive. O soluție mai generală, și poate chiar mai straight-forward, se bazează pe sume parțiale, și am explicat-o aici. Dezavantajul este că necesită un vector de frecvență, care în cazul numerelor negative ar trebui decalat. Nu mai zic că, dacă lucrăm cu numere ceva mai mari, acesta ar trebui transformat într-un tabel de hashing. Pe scurt, soluția cu Two-Pointers este mai simplă și nu necesită memorie auxiliară

Problema 2.

Pentru un număr natural pp cuprins între 11 și 101000010^{10\,000} să se determine două numere naturale ll și rr astfel încât l(l+1)r=pl \cdot (l + 1) \cdots r = p Se garantează că există o soluție cu 1lr1000001 \le l \le r \le 100\,000 (link)

În principiu, putem folosi direct ideea de la problema precedentă, deoarece șirul produselor parțiale ale secvenței 1,2,3,\langle 1, 2, 3, \ldots \rangle este și el (strict) monoton. Problema este că nouă deja ni se dau niște numere foarte mari. E prea greu să lucrăm și cu produsele lor. Aici intervine o tehnică foarte drăguță, numită logaritmare, care se bazează pe faptul că

log(ab)=log(a)+log(b)\log(a \cdot b) = \log(a) + \log(b)

indiferent de baza aleasă pentru logaritm. Prin urmare, în loc să calculăm produse de numere mari, putem calcula sume din logaritmii lor. Logaritmii naturali de exemplu. Aceștia încap lejer pe double.

Tot ce mai rămâne de făcut este să logaritmăm numărul dat, pentru că asta e valoarea la care trebuie să ajungă suma noastră. Știm din enunț că pp se poate scrie drept produsul unor numere mai mici decât 10510^5 de unde e clar că descompunerea sa în factori primi nu poate conține niciun factor mai mare de 10510^5 Așadar, putem aplica algoritmul clasic de factorizare, adunând pe parcurs logaritmii necesari. Deci, în ceea ce privește operațiile cu numere mari, avem nevoie doar de împărțirea la un număr mic.

Dar încă n-am terminat, pentru că am lua time limit cu sursa asta. Trebuie să mai optimizăm un lucru, și anume numărul de împărțiri efectuate. În loc să-l împărțim pe pp la un număr mic xx de foarte multe ori, îl putem împărți o dată și bine la o putere mare a acestuia. Mai exact, la x[logx2109]x^{[\log_x 2 \cdot 10^9]} unde 21092 \cdot 10^9 este (aproximativ) valoarea maximă a tipului int. După aceea, vom face și împărțiri direct la xx cât mai este nevoie. Aici aveți sursa completă, iar mai jos doar partea relevantă.

double target = 0;
for (int prime : sieve) {
if (p.isOne())
break;
if (p % prime == 0) {
int pwr = 1, exp = 0, add = 0;
while (pwr <= 2e9 / prime) {
add++;
pwr *= prime;
}
while (p % pwr == 0) {
exp += add;
p /= pwr;
}
while (p % prime == 0) {
exp++;
p /= prime;
}
target += log(prime) * exp;
}
}
double sum = 0;
int l = 1, r = 1;
while (abs(sum - target) > 1e-6)
if (sum > target)
sum -= log(l++);
else
sum += log(++r);
cout << l << ' ' << r << '\n';

Problema 3.

Se dă un vector vv de nn numere naturale. Să se determine câte subsecvențe ale lui vv conțin între xx și yy elemente distincte. (link)

În primul rând, trebuie să scăpăm de xx și yy Nu putem folosi Two-Pointers dacă trebuie să ținem cont simultan de două restricții similare – una de maxim și una de minim. Rezolvarea acestui inconvenient este foarte simplă: Reducem problema la a calcula f(k)f(k) numărul de subsecvențe care conțin cel mult kk elemente distincte. Astfel, răspunsul va fi f(y)f(x1)f(y) - f(x - 1)

Să ne imaginăm că în loc de cel mult avem exact kk elemente distincte. Putem aplica Two-Pointers ca până acum. Inițializăm secvența curentă cu [1,0][1, 0] și repetăm următorul procedeu până când terminăm de explorat fiecare rr posibil: Dacă avem mai puțin de kk elemente distincte, îl incrementăm pe rr iar dacă avem mai mult de kk îl incrementăm pe ll Frecvența valorilor luate în considerare poate fi ținută într-un unordered_map, iar numărul acestora într-o variabilă cnt\mathit{cnt}

Pentru a trece de la exact la cel mult, nu avem decât ca, pentru fiecare rr de la 11 la nn să adăugăm valoarea rl+1r - l + 1 la răspuns: Știm că ll este cel mai mic ll' astfel încât s(l,r)ks(l', r) \le k de unde ll' poate lua rl+1r - l + 1 valori.

auto count = [&](int max) {
int64_t ans = 0;
unordered_map<int, int> frq;
int l = 1, cnt = 0;
for (int r = 1; r <= n; r++) {
if (++frq[v[r]] == 1)
while (++cnt > max) {
if (--frq[v[l]] == 0)
cnt--;
l++;
}
ans += r - l + 1;
}
return ans;
};
cout << count(y) - count(x - 1) << '\n';

Problema 4.

Se dă un vector vv indexat de la 11 format din nn numere întregi, ordonate crescător. Să se determine indicii a două elemente din vv care au suma egală cu kk Cele două elemente trebuie să fie situate pe poziții diferite. Dacă nu există soluție, se va returna perechea (0,0)(0, 0) De exemplu, pentru v=4,1,0,3,7,9v = \langle -4, -1, 0, 3, 7, 9 \rangle și k=2k = 2 un răspuns posibil este (2,4)(2, 4) (link)

De data aceasta, cei doi pointeri nu mai pot merge în aceeași direcție: Fie că-l incrementăm pe ll sau pe rr suma dintre v[l]v[l] și v[r]v[r] tot în sus va merge, pentru că vectorul este sortat. Însă, noi trebuie să avem posibilitatea de a o și micșora. De aceea, pe ll îl vom itera de la stânga la dreapta, iar pe rr de la dreapta la stânga.

Când suma curentă este mai mică decât kk îl incrementăm pe ll înlocuindu-l astfel cu un număr mai mare (sau egal). Similar, când suma depășește target-ul, îl decrementăm pe rr înlocuindu-l cu un număr potențial mai mic. Ne oprim când lrl \ge r

În mod evident, complexitatea algoritmului este O(n)O(n) Repet, ideea funcționează doar pentru că vectorul este sortat. Demonstrația corectitudinii se bazează pe un invariant foarte asemănător cu cel descris la prima problemă, așa că o las ca temă pentru cititor.

int l = 1, r = n;
while (l < r) {
if (v[l] + v[r] == k)
return make_pair(l, r);
if (v[l] + v[r] < k)
l++;
else
r--;
}
return make_pair(0, 0);

Problema 5.

Se dă un vector vv indexat de la 11 format din nn numere întregi. Să se determine indicii a trei elemente din vv care au suma egală cu 00 Cele trei elemente trebuie să fie situate pe poziții diferite. Dacă nu există soluție, se va returna tripleta (0,0,0)(0, 0, 0) (link)

Cele trei numere aa bb și cc trebuie să verifice așadar relația a+b+c=0a + b + c = 0 Altfel spus, a+b=ca + b = -c Păi, pentru un cc fixat, răspunsul se obține rezolvând problema precedentă pe vectorul obținut prin ștergerea lui cc unde k=ck = -c Partea cu ștergerea lui cc din vector pare complicată, pentru că am obține doi noi subvectori, unul la stânga la cc și unul la dreapta sa. Aceștia ar trebui tratați ca și cum ar fi unul singur atunci când aplicăm Two-Pointers pe ei. Însă, impunând ca cc să fie cel mai din dreapta element dintre cele trei, va fi de ajuns să-i căutăm pe aa și bb doar în stânga sa.

Până acum, complexitatea este de ordinul O(n2)O(n^2) Un nn de la iterarea lui cc și altul de la căutarea liniară a elementelor aa și bb în stânga lui. Mai trebuie doar să sortăm vectorul inițial, pentru că altfel n-am putea aplica Two-Pointers pentru aa și bb Asta înseamnă încă un O(nlogn)O(n \log n) dar asta nu influențează complexitatea, deoarece n2n^2 crește mai repede. Atunci când sortăm vectorul, trebuie avut grijă să nu pierdem indicii inițiali ai elementelor în vv

vector<pair<int, int>> w(n + 1);
for (int i = 1; i <= n; i++)
w[i] = make_pair(v[i], i);
sort(w.begin() + 1, w.end());
for (int i = 3; i <= n; i++) {
int l = 1, r = i - 1;
while (l < r) {
if (w[l].first + w[r].first == -w[i].first)
return make_tuple(w[l].second, w[r].second, w[i].second);
if (w[l].first + w[r].first < -w[i].first)
l++;
else
r--;
}
}
return make_tuple(0, 0, 0);

Problema 6.

Se dă un vector vv de nn numere naturale. Să se ordoneze elementele sale în așa fel încât cele pare să fie situate la început, iar cele impare la sfârșit. Sortarea trebuie să fie efectuată in-place, adică nu ne putem ajuta de o structură de date auxiliară. De exemplu, o sortare posibilă pentru vectorul 3,2,1,4\langle 3, 2, 1, 4 \rangle este 4,2,3,1\langle 4, 2, 3, 1 \rangle (link)

În primul rând, vom trata toate numerele pare ca pe 00 și toate numerele impare ca pe 11 Putem sorta in-place vectorul dat iterând doi pointeri ll (de la stânga) și rr (de la dreapta), menținând la fiecare pas următorul invariant: Subsecvența [1,l][1, l] conține doar 00uri, iar subsecvența [r,n][r, n] conține doar 11uri. Când cu unul dintre pointeri găsim un element care nu e la locul lui (1\htmlClass{katexified}{(} 1 în stânga sau 00 în dreapta), îl ținem pe loc, până când va găsi și celălalt pointer un asemenea element. În acel moment, interschimbăm elementele v[l]v[l] și v[r]v[r] după care avansăm cu ambii pointeri.

Complexitatea este O(n)O(n) Iată și codul:

int l = 1, r = n;
while (l < r)
if (v[l] % 2 == 1 && v[r] % 2 == 0)
swap(v[l], v[r]);
else if (v[l] % 2 == 1)
r--;
else
l++;

Problema 7.

Se dă un vector vv format din nn numere din mulțimea {0,1,2}\{0, 1, 2\} Să se sorteze vectorul in-place. (link)

Aici nu ne mai putem descurca cu Two-Pointers. Avem nevoie de Three-Pointers Aceștia vor fi ll mm și rr Subsecvența [1,l1][1, l - 1] conține numai 00 [l,m1][l, m - 1] numai 11 [r+1,n][r + 1, n] numai 22 iar [m,r][m, r] conține elementele ce n-au fost încă explorate.

La fiecare pas, ne uităm la elementul v[m]v[m] Dacă este egal cu 00 trebuie mutat în prima secvență, așa că vom face swap între v[l]v[l] și v[m]v[m] după care incrementăm ambii pointeri. Dacă v[m]=1v[m] = 1 este foarte bine, îl lăsăm pe 11 acolo și incrementăm mmul. Dacă v[m]=2v[m] = 2 trebuie mutat către finalul vectorului. Facem swap între v[m]v[m] și v[r]v[r] după care îl decrementăm pe rr Din nou, complexitatea este liniară.

int l = 1, m = 1, r = n;
while (m <= r)
if (v[m] == 0)
swap(v[l++], v[m++]);
else if (v[m] == 1)
m++;
else
swap(v[m], v[r--]);

Sfârșit! Sper că acum este clar cum stă treaba cu tehnica Two-Pointers: care este intuiția din spate și de ce (sau când) este corectă Ca întotdeauna, dacă aveți vreo întrebare, nu ezitați să o lăsați mai jos într-un comentariu!

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii