h1(#dupadealuri). 'Solutia':algoritmiada-2019/runda-finala/solutii/dupadealuri problemei 'Dupadealuri':problema/dupadealuri

h1(#dupadealuri). 'Solutia':algoritmiada-2019/runda-finala/solutii/dupadealuri problemei 'Dupadealuri':problema/dupadealuri
 
*Solutie $O(N^3)$ – 20 de puncte*
 
Pentru orice subsecventa din sir, eliminam acea subsecventa si apoi verificam daca ce ne-a ramas este un palindrom. Complexitate <tex>O(N^3)</tex>.
 
*Solutie $O(N^2)$– 40 de puncte*
 
!solutiedupadealuri?imaginea1.jpg!
 
Orice palindrom posibil va arata ca in imaginea de mai sus, cu secventele <tex>L_1</tex> si <tex>L_2</tex> (posibil vide) de lungime egala si simetrice si cu palindromul $P$. Prin urmare o solutie ar fi sa mergem cu un iterator $l$ de la $0$ la $n/2$ care sa ne dea lungimea <tex>L_1</tex> si <tex>L_2</tex>, verificand ca prefixul rescpectiv sufixul de lungime $l$ sunt simetrice. Pentru fiecare $l$ valid putem gasi toate palindroamele $P$ care se invechineaza cu $l$ in <tex>O(N)</tex> pentru fiecare $l$ cu hashing sau cu Algoritmul lui Manacher. Complexitate totala <tex>O(N^2)</tex>.
 
*Solutie $O(N)$ – 100 de puncte.*
 
Solutia de <tex>O(N)</tex> e foarte similara cu cea de <tex>O(N^2)</tex> numai ca incercand pentru fiecare $l$ sa aflam rezultatul in <tex>O(1)</tex>. Facand mai intai Manacher pe tot sirul putem afla pentru fiecare punct $i$ palindromul maximal din $i$ ($nota:$ la Manacher $i$ nu e neaparat un numar natural datorita palindroamelor de lungime para).
Dupa cum se vede mai jos <tex>i-l_i<=L_1</tex> si <tex>L_1<=i</tex> daca si numai daca va exista un palindrom cu centrul in $i$ care sa se invechineze cu <tex>L_1</tex>. Dat fiind ca lungimile lui <tex>L_1</tex>, <tex>L_2</tex> care se invechineaza cu un palindrom cu centrul in $i$, sunt consecutive si stiute (<tex>i-l_i, i-l_i+1, </tex>…<tex> i-1,</tex> unde <tex>l_i</tex> este distanta de la i la capatul palindromului maximal) putem face Mo pentru a afla raspunsul final.
 
!solutiedupadealuri?imaginea2.jpg!
 
*Nota de final:* Aveti grija pentru fiecare $i$ la cine faceti suma partiala in functie de care dintre <tex>L_1</tex> si <tex>L_2</tex> va invechina palindromul cu centrul in $i$.