Palin3

Solutie: O(N³) pe fiecare din cele T teste, unde N este lungimea sirului

Vom rezolva fiecare test in parte, separat. Notam sirul pentru care dorim sa verificam proprietatea cu s, iar lungimea acestuia cu N. Vom considera ca elementele sirului sunt asezate pe pozitiile 0, 1, 2, ..., N-1. Vom folosi notatia i->j pentru secventa caracterelor de pe pozitiile i, i+1, ..., j.

Folosind metoda programarii dinamice, vom construi o matrice auxiliara D, avand urmatoarea semnificatie:

• D[i][j] = 1, daca secventa i->j poate deveni nula prin eliminari succesive de palindroame de lungime 3.
• D[i][j] = 0, daca secventa i->j nu are proprietatea de mai sus.

Vom initializa matricea noastra cu 0 pentru toate valorile lui i si j. Vom actualiza mai intai dinamica pentru secventele palindrom de lungime 3 existente in sirul nostru. Este evident ca o secventa de lungime 3 este de tip palindrom daca primul element al secventei este egal cu ultimul. Deci, o metoda simpla de a actualiza dinamica pentru secventele de lungime 3 este:

for ( int i = 0; i < n - 2; ++i )
    if ( s[i] == s[i + 2] )
        d[i][i + 2] = 1;

In continuare, va trebui sa actualizam dinamica si pentru secventele de lungime mai mare decat 3. Vom face acest lucru bazandu-ne pe urmatoarea afirmatie: O secventa i->j este o secventa ce respecta proprietatea daca se respecta cel putin una din urmatoarele proprietati:

• s[i] = s[j], si exista un k, i ≤ k ≤ j, astfel incat atat secventa i+1->k-1, cat si secventa k+1->j-1 respecta proprietatea din enunt. In acest caz, secventa i->j poate deveni nula, eliminand secventa i+1->k-1, secventa k+1->j-1, pentru ca in continuare sa eliminam si secventa formata din caracterele s[i], s[k], s[j].

• Exista un k, i ≤ k ≤ j, astfel incat atat secventa i->k, cat si secventa k+1->j respecta proprietatea din enunt. In acest caz, secventa i->j devine nula prin eliminarea acestor doua secvente.

Folosindu-ne de observatiile de mai sus, vom parcurge toate lungimile sirurilor pentru care trebuie sa actualizam matricea noastra, iar pentru fiecare lungime, vom seta capatul din stanga, i, capatul din dreapta va fi i + lungime - 1, si vom plimba indicele k intre aceste doua capete.

for ( int len = 4; len <= n; ++len ) // Parcurgem lungimile sirurilor de la 4 la n
    for ( int i = 0; i < n; ++i ) // Setam capatul din stanga
        if ( i + len - 1 < n ) { // Daca capatul din dreapta nu depaseste ultimul element al sirului
            int j = i + len - 1; // Retin capatul din dreapta in variabila j
            if ( s[i] == s[j] ) { // Daca elementele din capete sunt egale
                int k = i + 1; // Setez indicele din mijloc
                while ( k < j && !d[i][j] ) // Cat timp indicele nu depaseste intervalul si nu am gasit nici solutie
                    if ( d[i + 1][k - 1] && d[k + 1][j - 1] ) // Daca cele 2 secvente sunt bune
                        d[i][j] = 1; // Si secventa curenta este buna
            }

            if ( !d[i][j] ) { // Daca nu am setat pana acum secventa curenta ca fiind buna
                int k = i; // Setez indicele din mijloc
                while ( k < j && !d[i][j] ) // Cat timp indicele nu depaseste intervalul si nu am gasit nici solutie
                    if ( d[i][k] && d[k + 1][j] ) // Daca cele 2 secvente sunt bune
                        d[i][j] = 1; // Si secventa curenta este buna
            }
        }

In final, daca d[ 0 ][ n - 1 ] are valoarea 1, vom afisa DA. Altfel, vom afisa NU.

P.S. Cel mai probabil, va trebui sa aveti grija de un mic caz special, dar va descurcati voi!