Bazandu-ne pe aceeasi idee ca si la solutia anterioara, ne dam seama ca avem nevoie sa stim care sunt cele mai scumpe $K$ beri, dar nu avem nevoie de ele intr-o ordine fixa. De aceea, putem aplica algoritmul de pivotare Quick-Sort pentru gasirea celui de-al $(N-K+1)$-lea element in ordine crescatoare, problema cunoscuta si sub numele 'Statistici de ordine':problema/sdo.

h2. 'Palin3':problema/palin3
 
h4. $Solutie: O(N^3^) 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 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:
 
== code(cpp) |
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 &le; k &le; 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 &le; k &le; 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.
 
== code(cpp) |
for ( int len = 4; len <= n; ++len )
        for ( int i = 0; i < n; ++i )
            if ( i + len - 1 < n ) {
                int j = i + len - 1;
                if ( s[i] == s[j] ) {
                    for ( int k = i + 1; k < j; ++k )
                        if ( d[i + 1][k - 1] && d[k + 1][j - 1] )
                            d[i][j] = 1;
                }
 
                for ( int k = i; k < j; ++k )
                    if ( d[i][k] && d[k + 1][j] )
                        d[i][j] = 1;
            }
==
 
In final, daca $d[0][n - 1]$ va avea valoarea $1$, vom afisa $DA$. Altfel, vom afisa $NU$.
 

h2. 'Melodii':problema/melodii
Solutii prezentate de ==user(user="maritim" type="tiny")==.