h3.Probleme asemanatoare

* 'iepuri / preONI 2005':http://infoarena.ro/problema/iepuri

* 'Iepuri / preONI 2005':http://infoarena.ro/problema/iepuri

* 'Nice Patterns Strike Back / SGU':http://acm.sgu.ru/problem.php?contest=0&problem=197
* 'Fibo / .campion 2003':http://campion.edu.ro/problems/3/106/fibo.htm

* 'Problema celor $N$ regine [ clasica ] & co.':http://acm.fzu.edu.cn/reference/Search%20Techniques.htm
* 'Dame2 / Summer Challenge 2007':problema/dame2

h2. Rfinv

h2. 'Rfinv':problema/rfinv

h3. Solutie de complexitate $O(N^4^)$

h3. Probleme asemanatoare

* 'rf / Happy Coding 2006':problema/rf

* 'Rf / Happy Coding 2006':problema/rf
 
h2. 'Pali':problema/pali
 
Se va calcula $pmin[i]$ = numarul minim de palindroame in care poate fi impartit sirul format din primele $i$ caractere ale sirului dat.
 
h3. Solutia 1
 
Vom avea $pmin[0] = 0$ si $pmin[i] = 1 + min { pmin[j] | subsirul j+1,..,i este un palindrom }$, cu $0 ≤ j ≤ i-1$. Pentru a determina rapid daca subsirul dintre $2$ pozitii $k$ si $l$ este un palindrom, vom calcula o matrice $Pali[k][l]$, avand valorile $1$ si $0$, daca subsirul dintre pozitiile $k$ si $l$ este palindrom sau nu. Vom avea $Pali[k][l] = 1$, daca $sir[k] = sir[l]$ si $Pali[k+1][l-1]=1$ (pentru cazul in care {$l-k ≥ 2$}). Pentru ca aceasta solutie sa se incadreze in timp, va trebui ca matricea sa o calculam coloana cu coloana, pe masura ce avem nevoie de valorile din ea.
 
h3. Solutia 2
 
Vom incerca sa calculam valorile $pmin[i]$ treptat. Vom parcurge pozitiile de la $1$ la $N$ si vom incerca sa incepem un palindrom avand centrul in pozitia $i$ (pentru cazul unui palindrom de lungime impara), respectiv avand centrul la pozitiile $i$ si $i+1$ (pentru cazul unui palindrom de lungime para). Ideea importanta este ca, atunci cand ajungem la pozitia $i$, toate valorile $pmin[j]$, cu $j < i$ au fost calculate, iar valorile $pmin[k]$, $k > i$, au niste valori partiale (adica valorile calculate nu sunt inca finale, ele mai putand sa scada ulterior). Vom extinde treptat cat putem de mult un palindrom in jurul pozitiei $i$ (respectiv pozitiilor $i$ si {$i+1$}); la fiecare pas de extindere, vom incerca sa incrementam palindromul de la lungimea curenta $L$, la lungimea $L+2$ (pentru aceasta verificam caracterele din capatele palindromului); inainte de a realiza extinderea, vom incerca sa folosim palindromul curent in cadrul unei solutii - mai exact, vom avea posibilitatea ca valoarea $pmin[i-(L+1)/2]+1$ sa fie folosita pentru a micsora valoarea lui $pmin[i+(L+1)/2-1]$ (pentru cazul lungimii impare), respectiv valoarea $pmin[i-L/2]+1$ poate fi folosita pentru a micsora valoarea lui $pmin[i+L/2]$ (pentru cazul lungimii pare).
 
Complexitatea ambelor solutii este $O(N^2^)$, insa a doua solutie merge mai repede, in practica, deoarece ia in considerare numai palindroamele valide (care pot fi cel mult {$O(N^2^)$}).

h2. Pali

h2. Furnica