Par

Paa

h1(#par). 'Par':problema/par

h1(#patrulatere). 'Par':problema/par

Exista mai multe solutii la aceasta problema. Folosind programare dinamica putem calcula $A[i][j]$, numarul minim de inversari care trebuie facut pentru a obtine o secventa corect parantezata. $A[i][j]$ se poate obtine din $A[i+1][j-1]$ (avem o secventa corect parantezata in interior) sau din $A[i][k]+A[k+1][j]$ (concatenam doua secvente corect parantezate) pentru $k$ intre $i+1$ si $j-1$. Complexitatea va fi $O(N^3^)$. O idee mai buna ar fi sa calculam $C[i][j]$ numarul minim de inversari astfel incat daca am luat in calcul doar primele $i$ caractere vor ramane $j$ paranteze deschise care trebuie inchise in continuare. $C[i][j]$ poate proveni doar din $C[i-1][j-1]$ sau $C[i-1][j-1]$, deci complexitatea va fi $O(N^2^)$, suficienta pentru a obtine 100 puncte. Aceasta nu este insa cea mai buna solutie, exista si o solutie greedy care ruleaza in timp liniar. Ne imaginam ca avem o stiva in care tinem parantezele deschise care le avem la un moment dat. Procesam apoi sirul initial de paranteze. Daca paranteza curenta este inchisa si in stiva se afla macar o paranteza deschisa, eliminam din stiva o paranteza deschisa si trecem mai departe. Daca paranteza curenta este inchisa si in stiva nu se afla nicio paranteza deschisa atunci inversam paranteza curenta si o introducem in stiva. Daca paranteza curenta este deschisa o introducem in stiva. Dupa ce am parcurs tot sirul initial trebuie ca in stiva sa existe un numar par de paranteze deschise. Pentru a obtine un numar minim de inversari trebuie inversate exact jumatate din ele.

h2. Verificati sa fie pagina private pana dupa terminarea concursului

public

private