|
Titlul: 264 PScPld Scris de: ditzone din August 03, 2006, 21:56:40 Aici puteţi discuta despre problema PScPld (http://infoarena.ro/problema/pscpld).
Titlul: Raspuns: 264 PScPld Scris de: Paul-Dan Baltescu din 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? :-k (adica nu respecta exemplul de mai jos din solutie) Titlul: Raspuns: 264 PScPld Scris de: Cosmin Negruseri din August 06, 2006, 17:18:21 Mda, ai dreptate, editez imediat.
Titlul: Raspuns: 264 PScPld Scris de: Andrei Grigorean din August 07, 2006, 20:38:49 =D> :winner1:
frumoasa rezolvarea in O(n) si poate fi folosita si in alte prob cu palindroame. Titlul: Raspuns: 264 PScPld Scris de: Savin Tiberiu din 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. Titlul: Raspuns: 264 PScPld Scris de: Paul-Dan Baltescu din 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.
Titlul: Raspuns: 264 PScPld Scris de: Savin Tiberiu din August 08, 2006, 11:26:36 aha ms
Titlul: Raspuns: 264 PScPld Scris de: David si Goliat din 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 ?? :? 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); Titlul: Raspuns: 264 PScPld Scris de: Paul-Dan Baltescu din 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. :-' Titlul: Raspuns: 264 PScPld Scris de: David si Goliat din August 08, 2006, 14:59:19 Am facut cum ai zis tu si tot imi iese din timp ....
Titlul: Raspuns: 264 PScPld Scris de: Paul-Dan Baltescu din 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.
Titlul: Răspuns: 264 PScPld Scris de: Bozianu Ana din 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). Titlul: Răspuns: 264 PScPld Scris de: Marius Stroe din 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. :) Titlul: Răspuns: 264 PScPld Scris de: Valeriu Motroi din Septembrie 03, 2016, 19:03:19 Stie cineva cum se rezolva problema aceasta folosind Palindromic Tree?
|