h2. 'Palindroame':problema/palind

Pentru a avea solutie este necesar ca cel mult un singur caracter sa apara in sir de un numar impar de ori. In mod evident, nu vom inversa niciodata o pereche de caractere alaturate identice. Din acest motiv, in cadrul palindromului pe care il vom obtine, prima aparitie a unui caracter va fi "imperecheata" cu ultima aparitie a acelui caracter, a doua aparitie cu penultima s.a.m.d. In felul acesta, fiecare pereche defineste un interval $(a,b)$, $a$ reprezentand pozitia caracterului din stanga din cadrul perechii, iar $b$ reprezentand pozitia caracterului din dreapta din cadrul perechii. Singura conditie pentru ca numarul de inversiuni sa fie minim este sa nu ajungem sa inversam niciodata intre ele capetele a $2$ intervale care sunt incluse unul intr-altul. Pornind de la aceasta observatie, putem alege mereu intervalul corespunzator primului element al sirului si sa ducem pe ultima pozitie a sirului capatul dreapta al acestui interval, ramanand apoi cu un sir mai mic. In cazul in care primul element al sirului este caracterul ce trebuie sa se afle in mijlocul palindromului (pentru numar impar de caractere), atunci vom alege intervalul ce corespunde ultimei pozitii a sirului. Vom repeta acest procedeu pana cand ramanem cu un sir de lungime $0$ sau $1$.

Pentru a avea solutie este necesar ca maxim un singur caracter sa apara in sir de un numar impar de ori. In mod evident, nu vom inversa niciodata o pereche de caractere alaturate identice. Din acest motiv, in cadrul palindromului pe care il vom obtine, prima aparitie a unui caracter va fi "imperecheata" cu ultima aparitie a acelui caracter, a doua aparitie cu penultima s.a.m.d. In felul acesta, fiecare pereche defineste un interval $(a,b)$, $a$ reprezentand pozitia caracterului din stanga din cadrul perechii, iar $b$ reprezentand pozitia caracterului din dreapta din cadrul perechii. Singura conditie pentru ca numarul de inversiuni sa fie minim este sa nu ajungem sa inversam niciodata intre ele capetele a $2$ intervale care sunt incluse unul intr-altul. Pornind de la aceasta observatie, putem alege mereu intervalul corespunzator primului element al sirului si sa ducem pe ultima pozitie a sirului capatul dreapta al acestui interval, ramanand apoi cu un sir mai mic. In cazul in care primul element al sirului este caracterul ce trebuie sa se afle in mijlocul palindromului (pentru numar impar de caractere), atunci vom alege intervalul ce corespunde ultimei pozitii a sirului. Vom repeta acest procedeu pana cand ramanem cu un sir de lungime $0$ sau $1$.

h2. 'Lungimi de interval':problema/linterv

h2. 'Curse de cai':problema/cai

Vom sorta caii lui Gigel si Ionel in ordine descrescatoare si ii vom renumerota conform acestei ordini. Vom considera ca Gigel decide pentru fiecare cal al lui Ionel, in ordinea sortata, ce cal de-al sau sa ii opuna in cursa. Solutia prezentata in continuare se bazeaza pe urmatoarea observatie. Sa presupunem ca Gigel a decis ce cai de-ai sai vor concursa impotriva primilor $i$ cai ai lui Ionel si urmeaza sa decida pentru al $i+1-lea$ cal. Singurele doua variante fezabile pe care le are Gigel este sa aleaga cel mai bun cal al sau (dintre cei ramasi) si sa il puna sa concureze cu al $i+1$-lea cal al lui Ionel sau sa aleaga cel mai prost cal al sau. Vom calcula o matrice $C[i][j]$ reprezentand costul maxim pe care il poate obtine Gigel daca i-au mai ramas caii de la $i$ la $j$ (asta inseamna ca toti caii de la $1$ la $i-1$ au fost deja selectati si la fel si toti caii de la $j+1$ la $N$; de aici rezulta ca Gigel a ales dja adevrsai pentru primii $N-j+i-1$ cai de-ai lui Ionel si acum trebuie sa aleaga adversar pentru urmatorul cal al lui Ionel). $C[i][j]$ se calculeaza pe baza lui $C[i+1][j]$ (daca Gigel alege cel mai bun cal al sau impotriva calului curent al lui Ionel) sau pe baza lui $C[i][j-1]$ (daca elege cel mai prost cal al sau), alegandu-se varianta de cost maxim.

Vom sorta caii lui Gigel si Ionel in ordine descrescatoare si ii vom renumerota conform acestei ordini. Vom considera ca Gigel decide pentru fiecare cal al lui Ionel, in ordinea sortata, ce cal de-al sau sa ii opuna in cursa. Solutia prezentata in continuare se bazeaza pe urmatoarea observatie. Sa presupunem ca Gigel a decis ce cai de-ai sai vor concursa impotriva primilor $i$ cai ai lui Ionel si urmeaza sa decida pentru al $i+1-lea$ cal. Singurele doua variante fezabile pe care le are Gigel este sa aleaga cel mai bun cal al sau (dintre cei ramasi) si sa il puna sa concureze cu al $i+1$-lea cal al lui Ionel sau sa aleaga cel mai prost cal al sau. Vom calcula o matrice $C[i][j]$ reprezentand costul maxim pe care il poate obtine Gigel daca i-au mai ramas caii de la $i$ la $j$ (asta inseamna ca toti caii de la $1$ la $i-1$ au fost deja selectati si la fel si toti caii de la $j+1$ la $N$; de aici rezulta ca Gigel a ales deja adversari pentru primii $N-j+i-1$ cai de-ai lui Ionel si acum trebuie sa aleaga adversar pentru urmatorul cal al lui Ionel). $C[i][j]$ se calculeaza pe baza lui $C[i+1][j]$ (daca Gigel alege cel mai bun cal al sau impotriva calului curent al lui Ionel) sau pe baza lui $C[i][j-1]$ (daca elege cel mai prost cal al sau), alegandu-se varianta de cost maxim.

h2. 'Cercuri':problema/cercuri