Note de curs, clasele 9-10, 21 noiembrie 2013

From Algopedia
Jump to: navigation, search

Probleme de la barajul trecut

Dacă este nevoie, vom discuta problemele Avioane și Capitala.

Algoritmi pe vectori și matrice

Există mulți algoritmi clasici pe vectori și matrice, cu principii care reapar des. Trecem prin ei, ca să ne asigurăm că îi cunoașteți.

Problema majorității

Se dă un vector. Să se identifice (dacă există) un element care apare de cel puțin n/2 + 1 ori. Există trei algoritmi liniari:

  • eliminarea numerelor în perechi; este cel mai simplu și nu necesită memorie suplimentară
  • găsirea medianului cu algoritmul de selecție; modifică vectorul;
  • construim o tabelă hash care mapează valori la frecvențe; necesită memorie suplimentară

Minimum over a sliding window (MSW)

Se dă un vector. Să se găsească min(v[i], v[i + 1], ..., v[i + k - 1]) pentru fiecare i = 0, 1, ..., n - k.

Există o soluție în O(n) amortizat care folosește un deque (o coadă cu două capete). Găsiți implementarea în media:msw.cpp.

La nevoie, soluția cu heap este mai simplu de găsit și merge în O(n log k).

Subsecvența de sumă maximă

Se dă un vector. Să se găsească o subsecvență (continuă) de sumă maximă.

Soluția în O(n) se face cu programare dinamică. Felicitări, ați învățat programare dinamică. :-)

Dreptunghiul de sumă maximă

Se dă o matrice de numere întregi. Să se găsească dreptunghiul de sumă maximă.

Algoritmul naiv funcționează în O(n6): generează toate dreptunghiurile, care sunt O(n4), și îi calculează suma fiecăruia în O(n2).

O îmbunătățire până la O(n4): precalculăm s[i][j] = suma elementelor din dreptunghiul (1, 1) - (i, j). Apoi generăm în continuare toate dreptunghiurile, dar putem calcula suma fiecăruia în O(1).

Putem ajunge la O(n3). Pentru fiecare pereche de rânduri i și j, căutăm în O(n) coloanele k și l care ne dau dreptunghiul maxim. Pentru aceasta, dorim să calculăm rapid suma elementelor dintre rândurile i și j pe fiecare coloană. Facem aceasta observând că actualizarea sumelor de la perechea (i, j) la (i, j + 1) se face în O(n). Apoi, pe vectorul de sume, apelăm algoritmul 1D de subsecvență de sumă maximă.

Dreptunghiul de sumă maximă de dimensiune p x q

Ca mai sus, dar dreptunghiul găsit trebuie să aibă o dimensiune impusă, p x q.

Soluția naivă este în O(n4), căci sunt O(n2) dreptunghiuri și fiecare se calculează în O(n2).

Pentru o soluție în O(n2), trebuie să precalculăm toate sumele de p elemente pe linie, respectiv q pe coloană. Apoi putem deplasa dreptunghiul la dreapta și în jos în O(1).

Maximum gap

Se dă un vector nesortat; să se găsească distanța maximă între două elemente consecutive în vectorul sortat.

Soluția naivă sortează vectorul, deci este O(n log n).

Soluția în O(n) folosește principiul cutiei (principiul lui Dirichlet):

  • Găsește minimul și maximul, min și max.
  • Împarte (conceptual) intervalul [min-max] în n-1 intervale.
  • Plasează cele n-2 numere (fără min și max) în intervale
  • La fiecare plasare, actualizează minimul și maximul pentru fiecare interval. Acestea pot fi nule dacă un interval este gol.
  • Deoarece există n-2 numere și n-1 intervale, trebuie să existe un interval gol.
  • Așadar, distanța maximă va fi precis cel puțin de mărimea unui interval. Ea nu poate apărea între două numere din același interval.
  • Parcurge intervalele de la stânga la dreapta și returnează distanța maximă dintre maximul unui interval și minimul următorului interval care nu este gol.

Șmenul lui Mars

Vom perpetua tradiția acestui nume, în lipsa altului mai bun. :-) Șmenul lui Mars este bine explicat la infoarena.

Exemple de probleme care necesită această tehnică: flori, flori1.

Totuși, atenție la cuvântul „șmen”! În forma lui simplă, șmenul 2D necesită O(n2) memorie, căci reținem un număr suplimentar pe fiecare poziție din matrice. De fapt, avem nevoie doar de memorie O(n + e), unde e este numărul de evenimente. Procedăm astfel:

  • stocăm un vector de liste, câte unul pentru fiecare linie a matricei
  • citim evenimentele și le inserăm în listele corespunzătoare liniilor de început și de sfârșit, câte două evenimente în fiecare listă. Așadar, pentru dreptunghiul (l1, c1) - (l2, c2) de valoare x, vom insera evenimentele (c1, x) și (c2, -x) în lista corespunzătoare liniei l1, respectiv evenimentele (c1, -x) și (c2, x) în lista corespunzătoare liniei l2.
  • pentru calcularea matricei finale, marcurgem matricea pe linie și procesăm evenimentele de pe acea linie. Folosim memorie O(n) pentru a rezolva șmenul lui Mars 1D.

Dreptunghiul maxim de sub histogramă

Se dă o histogramă, adică o funcție formată din trepte la diverse înălțimi. Datele de intrare sunt doi vectori de înălțimi și lățimi. Să se găsească aria celui mai mare dreptunghi care poate fi încadrat sub histogramă. Problema Skyline cere exact acest algoritm.

Varianta naivă rulează în O(n2). Pentru fiecare bloc i, dorim să aflăm aria maximă a unui dreptunghi de acel bloc. Acest dreptunghi se întinde în stânga și în dreapta până la primele dreptunghiuri mai joase decât h[i]. Avem n dreptunghiuri și fiecare din ele se poate întinde pe O(n) blocuri.

Rezolvarea în O(n) menține o stivă ordonată. Pentru pasul i, avem nevoie de stiva ordonată a blocurilor crescătoare până la i. Dacă blocul curent este mai jos decât vârful stivei, atunci putem calcula aria maximă pentru dreptunghiul determinat de blocul din vârful stivei. Acel bloc se întinde în stânga până la elementul anterior din stivă, iar la dreapta până la blocul curent. Apoi eliminăm elementul din vârful stivei.

Găsiți implementarea în media:largest-rectangle-under-histogram.cpp. Problema se simplifică un pic dacă toate blocurile au lățimea egală cu 1 (caz în care la intrare primim doar vectorul de înălțimi).

Dreptunghiul gol de arie maximă (Largest empty rectangle)

Se dă o matrice de 0 și 1. Să se găsească dreptunghiul de arie maximă care conține doar 0. O problemă care cere acest algoritm este dreptunghi1.

Din nou, soluția naivă este O(n6), testând toate dreptunghiurile. Din nou, putem reduce complecitatea la O(n4) precalculând suma elementelor din fiecare dreptunghi (1, 1) - (i, j).

Iată o abordare diferită care duce tot la O(n4). Fixăm colțul din stânga-sus, apoi răspundem la întrebări de tipul „care este aria maximă a unui dreptunghi care începe la (i1, j1) și se termină pe linia i2”? Avem O(n3) astfel de întrebări. Răspunsul la fiecare întrebare este dat de numărul minim de zerouri spre dreapta pe liniile i1, i1 + 1, ..., i2. Putem calcula răspunsul în O(n), refolosind răspunsul de la tripletul (i1, j1, i2 - 1) și parcurgând linia i2 spre dreapta pentru a număra zerourile.

Această abordare poate fi îmbunătățită ușor la O(n3) precalculând, pentru fiecare punct (i, j), numărul de zerouri la dreapta.

În final, observăm că putem trata toate perechile (i1, j1) de pe aceeași coloană j1 în O(n). Subproblema ne cere exact să aflăm cel mai mare dreptunghi de sub histogramă, unde histograma constă din blocuri de lățime 1 și înălțimi egale cu numărul de zerouri de pe fiecare linie.

Range Minimum Query (RMQ)

Această problemă intră în categoria clasică a problemelor de preprocesare și interogare (preprocessing and query). Se dă un vector de n numere, apoi se pun q întrebări de forma „care este elementul minim între pozițiile i și j inclusiv?”. Există un articol foarte bun despre RMQ la TopCoder.

Algoritmul naiv răspunde la fiecare întrebare pe măsură ce o primește. El face O(1) preprocesare (de fapt 0), dar răspunde la fiecare interogare în O(n).

La polul opus avem preprocesarea completă. Calculăm o matrice D[i][j] care reține răspunsurile tuturor întrebărilor posibile. Precalcularea cere O(n2) spațiu și durează O(n2) (cum facem?), după care putem răspunde la interogări în O(1). Dacă numărul de interogări este mic (mai mic de O(n2)), atunci preprocesarea este nerezonabil de scumpă.

O abordare diferită se bazează pe o metodă frecvent întâlnită de a reduce timpul și spațiul de la O(n) la O(sqrt(n)). Împărțim vectorul în n/k segmente de câte k elemente (strict vorbind sunt (n - 1) / k + 1 segmente). Calculăm minimul pe fiecare segment. Pentru o interogare (i, j), calculăm rapid minimul segmentelor incluse complet în intervalul (i, j) și calculăm separat minimul porțiunilor incomplete de segment. Vom face, așadar, O(2k + n/k) operații. Această complexitate este minimă când k = sqrt(n) (de ce?). Necesarul de memorie este O(sqrt(n)). Preprocesarea durează O(n), iar interogările câte O(sqrt(n)).

Putem obține timpi și mai buni dacă construim o structură auxiliară D[i][j] cu semnificația „cel mai mic element dintr-un vector care începe la poziția i și are lungimea 2j”. Această structură are dimensiunea O(n log n) și poate fi calculată în O(n log n) (cum?). Apoi putem răspunde la interogări în O(1) (cum?). Un aspect interesant este: cum calculăm logaritmul în baza 2 al unui număr întreg?

Ca să recapitulăm,

Algoritm Memorie suplimentară Timp de preprocesare Timp de interogare
naiv 0 0 O(n)
preprocesare completă O(n2) O(n2) O(1)
segmente de câte sqrt(n) elemente O(sqrt(n)) O(n) O(sqrt(n))
segmente de lungimi 2j O(n log n) O(n log n) O(1)

Găsiți implementări în media:rmq-sqrt.cpp și media:rmq-log.cpp.

Există un algoritm cu preprocesare în O(n) și interogare în O(1), dar nu îl vom discuta astăzi. El se bazează pe arbori și funcționează în tandem cu algoritmul de aflare a celui mai jos strămoș comun (lowest common ancestor -- LCA).