Clasele 9-10 lecția 15 - 14 ian 2015

Programare dinamică

Vom continua cu probleme și optimizări din lecția trecută. Iată câteva probleme detaliate.

Număr format din 0 și 1, divizibil cu n

Enunț: Se dă un număr n ≤ 1.000. Să se găsească cel mai mic număr zecimal, format doar din cifre de 0 și 1, divizibil cu n. Exemple: pentru n = 3 numărul este 111. Pentru n = 7 numărul este 1001. Pentru n = 17, numărul este 11101.

Vezi și problema Ones and zeros (SPOJ).

Presupunând că nu avem nicio idee bună, cum rezolvăm problema prin backtracking? Să considerăm cazul n = 17. Trebuie să adunăm niște puteri ale lui 10, adică un subset al lui { 1, 10, 100, 1.000, ... }, astfel încât suma numerelor să fie minimă, iar suma resturilor modulo 17 să fie zero. Pentru a ne ușura munca putem precalcula resturile modulo 17 ale acestor puteri:

puterea	restul modulo 17
1	1
10	10
100	15
1.000	14
10.000	4
100.000	6
1.000.000	9
...	...

Vom genera apoi mulțimea submulțimilor în ordine crescătoare: 1, 10, 11, 100, 101, 110, 111, 1000... și vom aduna resturile corespunzătoare pozițiilor cu 1. De exemplu, pentru 1011, resturile corespunzătoare sunt 14 + 10 + 1 ≡ 8 (mod 17). Astfel vom descoperi că răspunsul este 11101, cu restul corespunzător 4 + 14 + 15 + 1 ≡ 0 (mod 17). Întrucât pentru anumite valori ale lui n răspunsul poate avea $O(n)$ cifre, această soluție este $O(2^{n})$.

Cum obținem o soluție polinomială? Mai întâi aflăm numărul de cifre. Pentru aceasta, trebuie să stocăm toate resturile distincte modulo n pe care le putem obține cu numere de k cifre. Pentru a trece la k + 1 cifre există două abordări asemănătoare, după cum adăugăm o cifră nouă la începutul la sfârșitul numerelor de k cifre. În continuare discutăm soluția care adaugă cifre la sfârșit.

Prima cifră a numărului este în mod necesar 1. Așadar, cu un număr de o cifră putem obține doar restul 1 (mod 17). La acesta putem adăuga fie 0, fie 1. Așadar, cu numere de două cifre putem obține resturile 10 sau 11 (mod 17). La 11, de exemplu, putem adăuga din nou 0 sau 1, obținând resturile 8 sau 9 (mod 17). În general, dacă cu k cifre putem obține restul r (mod 17), atunci cu k + 1 cifre vom putea obține resturile $10r$ sau $10r+1{\pmod {17}}$.

Rezultă tabelul:

nr. cifre	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
1		X
2											X	X
3									X	X						X	X
4						X	X	X	X				X	X	X	X
5	X	X	X	X	X	X				X	X	X	X	X	X	X	X

În acest moment ne putem opri, deoarece am găsit un mod de a obține restul 0 cu 5 cifre. Facem observația că restul 2 poate fi obținut în două moduri cu 5 cifre: 7 * 10 + 0 ≡ 2 (mod 17) dar și 12 * 10 + 1 ≡ 2 (mod 17). Această observație este necesară pentru pasul următor.

Știm că numărul are 5 cifre, dar care sunt ele? O primă variantă ar fi să ținem minte, pentru fiecare X din matrice, cine este „părintele” de pe rândul anterior care a cauzat completarea lui X. De exemplu, l-am bifat pe A[5][0] datorită lui A[4][5], căci 5 * 10 + 1 ≡ 0 (mod 17). Similar obținem lanțul de părinți A[5][0] → A[4][5] → A[3][9] → A[2][11] → A[1][1]. Verificăm dacă pe fiecare din aceste săgeți am adăugat un 0 sau un 1 și obținem, în ordine, cifrele 11101.

Din păcate, asta nu e tot. După cum spuneam, unele celule din matrice pot avea doi (sau mai mulți) părinți. Pe care dintre ei trebuie să-i urmăm? Care dintre ei generează numărul cel mai mic?

Pentru a afla numărul efectiv, este mai bună o abordare înainte. Știm că prima cifră este 1 (în mod banal), iar numărul are 5 cifre. Valoarea 10.000 contribuie cu restul 10.000 % 17 = 4. Lui 10.000 trebuie să-i adăugăm cel mai mic număr de 4 cifre care contribuie cu restul 13, căci 13 + 4 ≡ 0 (mod 17). Putem să punem un 0 pe poziția miilor? Nu, căci cu ultimele 3 cifre nu putem obține restul 13, conform tabelului de mai sus. Suntem deci obligați să punem un 1 pe poziția miilor, ceea ce contribuie cu restul 14. Apoi căutăm cel mai mic număr de 3 cifre care contribuie cu restul 16, căci 4 + 14 + 16 ≡ 0 (mod 17). Continuăm astfel până când obținem răspunsul 11.101.

Complexitatea acestui algoritm este $O(n^{2})$ ca timp și ca memorie. Remarcăm că, dacă s-ar cere doar numărul de cifre, nu am avea nevoie să stocăm toată matricea A. Am putea stoca doar ultimele două linii, cu memorie $O(n)$.

Soluție în O(n) (Alex Văleanu)

Această secțiune este scrisă de Alex Văleanu. Mulțumim!

Problema poate fi rezolvată și fără programare dinamică bazându-ne însă pe aproximativ aceeași idee pe care este structurată și soluția cu programare dinamică, construcția numărului cifră cu cifră.

Vom folosi un algoritm asemănător cu parcurgerea în lățime. Pornim cu o coadă vidă în care inserăm restul 1. La fiecare pas extragem un rest din coadă și încercăm să explorăm cele două resturi ce pot fi formate prin adăugarea cifrelor 0 și 1 la finalul restului curent. Dacă obținem un rest încă neexplorat îl adăugăm în coadă și continuăm algoritmul. Reconstituirea soluției se poate face recursiv dacă memorăm pentru fiecare rest „tatăl” său din parcurgerea BFS.

Complexitatea algoritmului este O(N) atât timp cât și memorie.

Probleme:

• http://www.spoj.com/problems/ONEZERO/
• http://www.infoarena.ro/problema/cifre4

Cod sursă:

• media:zero-unu-alex-văleanu.cpp

Distanța Levenshtein

Definim distanța Levenshtein ca fiind numărul minim de operații pentru a transforma un șir de caractere A în alt șir B, unde o operație poate fi:

• inserarea unui caracter oriunde în A;
• ștergerea unui caracter al lui A;
• modificarea unui caracter al lui A.

De exemplu, pentru a transforma șirul clopot în lopata avem nevoie de minim 3 operații:

• ștergem caracterul c: lopot;
• modificăm caracterul o în a: lopat;
• inserăm caracterul a: lopata.

Cum calculăm distanța Levenshtein? Dacă nu am avea nicio idee eficientă, hai să ne gândim la o soluție recursivă exponențială. Care este relația între ultimele caractere din A și B? Dacă sunt egale, putem renunța la ambele, iar distanța Levenshtein nu se modifică (de exemplu, distanța de la clopotxyz la lopataxyz este tot 3). Dacă ultimele caractere diferă, atunci:

• fie ultimul caracter din A va fi șters
• fie ultimul caracter din B va fi inserat
• fie ultimul caracter din A va fi modificat în ultimul caracter din B.

Nu avem cum altfel să justificăm existența ultimului caracter din B. Notând șirurile cu A[1..m] și B[1..n], obținem funcția recursivă:

  int lev(char *a, int m, char *b, int n) {
    if (!m) {
      // Dacă șirul A este vid, trebuie să inserez toate caracterele lui B
      return n;
    } else if (!n) {
      // Pentru a ajunge la șirul vid trebuie să ștergem toate caracterele lui A
      return m;
    } else if (a[m] == b[n]) {
      // Ultimele caractere coincid
      return lev(a, m - 1, b, n - 1);
    } else {
      return 1 + min(
        lev(a, m - 1, b, n),
        lev(a, m, b, n - 1),
        lev(a, m -1, b, n - 1));
    }
  }

De aici, urmăm raționamentul obișnuit. Întâi ne gândim să memoizăm valorile funcției. Cum șirurile A și B sunt constante, avem nevoie doar de o matrice D de m x n poziții. Apoi ne dăm seama că putem calcula sistematic valorile matricei, căci valoarea D[i][j] depinde doar de valorile din stânga, sus și stânga-sus:

  // Cazurile-limită
  for (int i = 0; i <= m; i++) {
    d[i][0] = i;
  }
  for (int j = 0; j <= n; j++) {
    d[0][j] = j;
  }

  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      if (a[i] == b[j]) {
        d[i][j] = d[i - 1][j - 1];
      } else {
        d[i][j] = 1 + min(d[i - 1][j], d[i][j - 1], d[i - 1][j - 1]);
      }
    }
  }

Pentru șirurile clopot și lopata obținem matricea:

	Φ	l	o	p	a	t	a
Φ	*0*	1	2	3	4	5	6
c	*1*	1	2	3	4	5	6
l	2	*1*	2	3	4	5	6
o	3	2	*1*	2	3	4	5
p	4	3	2	*1*	2	3	4
o	5	4	3	2	*2*	3	4
t	6	5	4	3	3	*2*	*3*

Dacă ni se cere doar distanța între șiruri, trebuie doar să tipărim D[m][n]. Dar dacă ni se cere și un set de operații? Pornim de la coordonatele (m, n) și mergem la stânga și în sus, conform acelorași reguli. Operațiile sunt:

• inserarea corespunde unei deplasări la stânga;
• ștergerea corespunde unei deplasări în sus;
• modificarea corespunde unei deplasări pe diagonală, numai dacă A[i] ≠ B[j].

Și în această problemă, dacă se cere doar distanța, nu și operațiile, putem folosi doar memorie $O(n)$ (ultimele două linii din matrice).

Discuție: cum se schimbă programul dacă permitem și inversarea a două caractere ca operație elementară?

Aici vom introduce tehnica de reducere a memoriei necesare printr-un factor de ${\sqrt {n}}$.

Numărul de parantezări

Enunț: Câte șiruri distincte există cu n paranteze deschise și n paranteze închise care să fie corect imbricate? De exemplu, șirul (())() este corect imbricat, pe când șirul (()))( nu este corect imbricat.

Problema poate fi formulată în multe alte feluri echivalente, de exemplu:

• Câte șiruri de n cifre 0 și n cifre 1 există astfel încât, pentru orice prefix, numărul de 1 să nu depășească numărul de 0?
• Câte drumuri Manhattan există de la coordonatele (0, 0) la (n, n), mergând doar la dreapta sau în sus, astfel încât la niciun moment traiectoria să nu depășească diagonala (0, 0) - (n, n)?

Și aici putem obține o relație de recurență pornind de la următoarea observație. În mod sigur prima paranteză este una deschisă. Ea trebuie să se închidă undeva în cuprinsul șirului, deci orice șir de paranteze S va avea forma generală

$S=(S_{1})S_{2}$

Șirurile $S_{1}$ și $S_{2}$ vor avea în total n - 1 perechi de paranteze, iar orice distribuire diferită între $S_{1}$ și $S_{2}$ conduce la soluții diferite. Fiecare dintre subproblemele pentru $S_{1}$ și $S_{2}$ se rezolvă la fel, recurent. Obținem deci formula:

$C(n)=\sum _{i=0}^{n-1}C(i)C(n-1-i)$, unde $C(0)=1$

Precizăm că acest șir este bine studiat. Termenii săi se numesc numerele lui Catalan și au formula explicită:

$C(n)={\frac {C_{2n}^{n}}{n+1}}$

Așadar, formula finală poate fi calculată în $O(n)$, dar am prezentat algoritmul $O(n^{2})$ în scopuri didactice.

Temă

• Tema 12 juniori