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³). 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²), 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.