Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 264 PScPld  (Citit de 3765 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
ditzone
Vizitator
« : August 03, 2006, 21:56:40 »

Aici puteţi discuta despre problema PScPld.
Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #1 : August 06, 2006, 10:32:42 »

Citat
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?  Think
(adica nu respecta exemplul de mai jos din solutie)
Memorat

Am zis Mr. Green
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #2 : August 06, 2006, 17:18:21 »

Mda, ai dreptate, editez imediat.
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #3 : August 07, 2006, 20:38:49 »

 Applause  Winner 1st place

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

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #4 : August 08, 2006, 10:36:34 »

Citat
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.
Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #5 : August 08, 2006, 11:15:42 »

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.
Memorat

Am zis Mr. Green
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #6 : August 08, 2006, 11:26:36 »

aha ms
Memorat
pocaitu
De-al casei
***

Karma: -26
Deconectat Deconectat

Mesaje: 141



Vezi Profilul
« Răspunde #7 : August 08, 2006, 13:22:48 »

 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 ?? Confused
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);
« Ultima modificare: August 08, 2006, 13:27:37 de către pocaitu » Memorat

This is not a signature ! I repeat, this is not a signature !
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #8 : August 08, 2006, 13:37:05 »

 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.  Whistle
Memorat

Am zis Mr. Green
pocaitu
De-al casei
***

Karma: -26
Deconectat Deconectat

Mesaje: 141



Vezi Profilul
« Răspunde #9 : August 08, 2006, 14:59:19 »

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

This is not a signature ! I repeat, this is not a signature !
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #10 : August 08, 2006, 16:14:58 »

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.
Memorat

Am zis Mr. Green
anna_bozianu
De-al casei
***

Karma: 5
Deconectat Deconectat

Mesaje: 111



Vezi Profilul
« Răspunde #11 : Ianuarie 16, 2008, 18:27:11 »

 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" ?
 
Citat
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(n2).
« Ultima modificare: Ianuarie 16, 2008, 18:30:13 de către Bozianu Ana » Memorat
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« Răspunde #12 : Februarie 17, 2009, 22:58:19 »

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. Smile
« Ultima modificare: Februarie 18, 2009, 12:48:07 de către Marius Stroe » Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
Djok
Client obisnuit
**

Karma: 10
Deconectat Deconectat

Mesaje: 71



Vezi Profilul
« Răspunde #13 : Septembrie 03, 2016, 19:03:19 »

Stie cineva cum se rezolva problema aceasta folosind Palindromic Tree?
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines