Papuci

Observam ca daca privim capatul din stanga al unei perechi ca o paranteza deschisa si capatul din dreapta ca o paranteza inchisa obtinem defapt un sir de parantezari valide. De asemenea daca inversam doua litere dintr-o pereche observam ca sunt afectate doar parantezarea care incepe exact dupa capatul din dreapta al perechii, parantezarea care incepe exact dupa capatul din stanga al perechii si cea care se termina exact inainte de capatul din dreapta al perechii (evident daca acestea exista). Vom rezolva problema cu ajutorul programarii dinamice. Sa presupunem ca avem o pereche x care are in interiorul ei perechile a₁ a₂ ... a_k care corespund unor alte parantezari corecte: ( a₁ a₂ ... a_k ). Vom calcula Min[ x ][ 0 ] ca fiind costul minim care se obtine pentru perechea x daca nu interschimbam caracterele si Min[ x ][ 1 ] costul minim care se obtine daca interschimbam parantezele. Acest cost se calculeaza luand in calcul doar ce se intampla in interiorul perechii de paranteze x. Pentru a calcula aceasta valoare am avea nevoie de valorile Min[ a₁ ][ 0 ], Min[ a₁ ][ 1 ], Min[ a₂ ][ 0 ], Min[ a₂ ][ 1 ] .... Apoi trebuie sa facem o noua dinamica in care vom calcula o matrice Cmin[ 2 ][ 2 ] in care prima valoare indica faptul daca am interschimbat sau nu caracterele din perechea a₁ si a doua valoare daca am interschimbat sau nu caracterele din perechea a₂. Putem calcula aceasta matrice in timp liniar. Dupa ce am calculat toate valorile Min[ i ][ 0 ] si Min[ i ][ 1 ] putem calcula raspunsul final luand in calcul numai relatiile care nu sunt incluse in alte relatii (vom avea un sir de genul (..)(..)(..)). Complexitatea pentru a calcula toate valorile necesare din dinamica este O(N), deoarece o pereche o accesam doar atunci cand calculam valorile pentru perechea de paranteza ce o include pe ea, dar numai pentru prima dintre acestea. Se pot obtine 100 de puncte si cu solutii de complexitate O(N*logN) care folosesc o sortare pentru a determina sirul de parantezari.