264 PScPld

[ditzone]

Aici puteţi discuta despre problema PScPld.

[•pauldb]

Solutia va pastra un sir LUNG unde LUNG[2i] reprezinta lungimea palindromului maxim centrat in caracterul i al sirului si LUNG[2i + 1] lungimea palindromului centrat intre caracterul i si i + 1 al sirului.

Acest fragment face parte din solutia oficiala si mi se pare gresit. Nu? 
(adica nu respecta exemplul de mai jos din solutie)

[•Cosmin]

Mda, ai dreptate, editez imediat.

[•wefgef]

  

frumoasa rezolvarea in O(n) si poate fi folosita si in alte prob cu palindroame.

[•devilkind]

sirul:  a    b    a    a   b    a     c   
LUNG: 1 0 3 0 1 6 1 0 x
indice: 1 2 3 4 5 6 7 8 9 10 11 12 13

si totusi dak ultimu caracter ar fi "a" atunci in locul lui x ar trebui sa fie 5, dar dupa algoritmu mentionat vine 3. Cel putin asa am inteles eu.

[•pauldb]

Nu, solutia iti garanteaza ca in x ai un palindrom de lungime cel putin 3 [deci asta nu mai trebuie sa verifici]. Apoi va trebui sa-l extinzi cat poti.

[•devilkind]

aha ms

[•pocaitu]

 dar daca sirul ar fi de forma
sirul   a     a     b   a    a     b   a   c
lung   1  1 1 0  4 0 1 6 1 0   x
indice 1  2  3 4 5 6 7 8 9 10 11
acuma lung [11] ar fi de cel putin 4 ?
eu spre exemplu , pt a remedia situatia asta dupa ce calculat lung[6] mai faceam un for :
""""""""""""""
for(d2=1,d1=i;d2<=lung;d2++,d1--);
      if(lung-d2+1>=l[d1])
       lung[d2+i]=lung[d1];
      else
       lung[d2+i]=lung-d2+1;
"""""""
dar imi iese din timp la ultimele 7 teste;
are cineva o alta idee ??
Sau poate imi iese din timp pt. ca la mine mai modific vectorul s punand elementele lui numai in pozitii impare?
spre ex s[]="aba" devine s[]="nimic,a,nimic,b,nimic,c);

[•pauldb]

 dar daca sirul ar fi de forma
sirul   a     a     b   a    a     b   a   c

atunci ai avea

lung   1 1 1 0 5 0 1 6 1 0   3 ...
indice 1 2 3 4 5 6 7 8 9 10 11

Si ca sa-ti raspund la intrebarea ta:

lung[11] = 3, desi lung[5]=5, deoarece palindromul "abaaba" nu garanteaza pentru "aabaa" ci pentru "aba". Asta se poate face O(1) luand minimul intre doua valori. 

[•pocaitu]

 Am facut cum ai zis tu si tot imi iese din timp ....
 

[•pauldb]

Verifica daca copiezi bine lungimile palindroamelor. Daca faci acolo vreo greseala si pui 0 algoritmul va functiona in continuare, doar ca vei avea solutia in n^2.

[•anna_bozianu]

 Totusi... nu inteleg cum se actualizeaza vectorul lung pentru a ramane in O(n).

 Inteleg din exemplu ca la calculul lui lung[9] se pleaca din valoarea 3 dar nu pot sa imi dau seama in ce moment primeste lung[9] valoarea 3 ? In momentul in care s-a calculat lung[6]=6 ? Se fac actualizarile in momentul in care se obtine un palindrom ce depaseste "zona actualizata" ?
 

Acum daca vrem sa calculam LUNG9 ar trebui sa ne extindem cat putem in lateral fata de b, dar observam ca centrul palindromului curent este continut in palindromul centrat la 6.

 Cum "observam" ? Poate cineva sa ma lamureasca si pe mine. E o idee extraordinara dar din pacate nu reusesc sa o inteleg. Orice incercare de a implementa ideea oficiala ma duce la 30 p cu TLE pe ultimele 7 adica nu ies in nici un fel din O(n²).

[•Marius]

Explicațiile nu arată mai nimic. Ar trebui modificat ce e scris în paranteză.

Le: Dacă totuși pui microscopul se va vedea că sunt îngroșate unele litere.

[•Djok]

Stie cineva cum se rezolva problema aceasta folosind Palindromic Tree?