565 Pali

[•DITzoneC]

Aici puteţi discuta despre problema Pali.

[•Cosmin]

Abia acum am vazut problema asta. Cred ca se poate O(N) sau cel mult O(N log N), nu O(N^2) cum zice in solutie.

[•gabitzish1]

Se poate ! http://infoarena.ro/job_detail/106914

[•Marius]

Ce se poate, O(N) sau O(N lgN)?

[•gabitzish1]

  e tot O(n^2)
Pentru un test in care sirul e format din elemente identice, are complexitate patratica.

[•nparfene2004]

Se pare ca nu rezolv bine problema... 
Totusi am o nelamurire: la testul 1 iau ok (10 puncte), la restul wrong answer sau TLE si totusi primesc in final 0 puncte. Cum e posibil?

[•klamathix]

Testele sunt grupate. Primesti punctaj pe o grupa doar daca ai ok pe toate testele din care e constituita, otherwise primesti 0 pe grupa respectiva. Toate problemele date la Happy Coding sunt in stilul asta, 0 sau 100.

[•dornescuvlad]

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

Nu inteleg chestia asta... cine e sir[k] si cine e sir[l] (caracterul de pe pozitia k, respectiv l) ?
si de ce Pali[k+1][l-1]=1  in caz ca l-k>=2 ?  

Stie cineva sa-mi raspunda ? Nu inteleg optimizarea asta...

Haideti ma va rog... cum calculez intr-o matrice a

• [y] daca sirul dintre x si y este palindrom

in cea mai buna complexitate

Nu posta consecutiv pe aceeasi tema! Modifica mesajele anterioare.

cum calculez intr-o matrice d[ i ][ j ] daca sirui dintre i si j este un palindrom?
intr-o complexitate cat mai mica///

Tu nu intelegi sa modifici mesajele anterioare?

Pai vad ca nimeni nu raspunde, desi majoritatea stiu .... am zis sa mai postez o data sa vada lumea

[•DraStiK]

Vlad, ia-o mai ușor cu atitudinea. Nimeni nu vrea sa stea sa dea indicații când aceasta problema a fost data la Happy Coding 2007.

Consulta articolul cu soluții dacă ai nelămuriri.

http://infoarena.ro/happy-coding-2007/solutii#pali

[•SpiderMan]

Pai a zis ca a citit-o dar nu stie ce scrie acolo si vrea sa-i explicati

[•dornescuvlad]

Vlad, ia-o mai ușor cu atitudinea. Nimeni nu vrea sa stea sa dea indicații când aceasta problema a fost data la Happy Coding 2007.

Consulta articolul cu soluții dacă ai nelămuriri.

http://infoarena.ro/happy-coding-2007/solutii#pali

Se si explica acolo ca sa intelegeti numa voi...
M-am uitat pe solutia aia si n-am inteles cum imi calc matricea

[•wefgef]

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

Nu inteleg chestia asta... cine e sir[k] si cine e sir[l] (caracterul de pe pozitia k, respectiv l) ?

Vectorul sir este un array de caractere in care se retine sirul din fisierul de intrare. Vrem sa calculam pentru oricare doi indici k si l daca susecventa sir[k], sir[k + 1], ... sir[l - 1], sir[l] este palindrom. Ne vom folosi de proprietatea urmatoare:

O subsecventa este palindrom daca:
1. Primul element este egal cu ultimul, adica sir[k] = sir[l]
2. Subsecventa fara caracterele din capete este tot un palindrom, adica daca sir[k + 1], sir [k + 2] ... sir[l - 2], sir[l - 1] este tot palindrom.

De aici rezulta recurenta de mai sus.

si de ce Pali[k+1][l-1]=1  in caz ca l-k>=2 ? 

Nu ai inteles bine ce se spune in articol. Poti folosi recurenta de mai sus pentru subsecvente de lungime >= 3. O reformulare ar fi:
Pentru subsecvente de lungime >= 3, ne vom folosi de proprietatea: Pali[k][l] = 1 daca si numai daca sir[k] = sir[l] si Pali[k + 1][l - 1] = 1.

[•dornescuvlad]

Multumesc, mi-am precalculat matricea de [LgMax][LgMax] cu propietatea ca A[k][l] este egal cu 1 daca si numai daca sirul dintre k si l este palindrom.....dar vad  ca am tle pe 6 teste, desi e O(N^2) ceea ce ar trebui sa intre in timp....care e optimizarea? cum fac sa retin mai putine coloane/linii  si sa le folosesc pe parcurs ce imi trebuiesc (asa cum scrie in solutia oficiala)
Mersi.

[•lucian666]

Salutare
La problema aceasta am folosit o dinamica in N^2 dar iau doar 0 pct cu 4 Corect si restul  TLE;
Am observat ca si in articolul cu solutii ,ambele solutii pt problema sunt N^2 ,deci nu inteleg de ce iau TLE.

[•vendetta]

În primul rand ce faci tu acolo e un n^3. Totuşi dacă vei reuşi să ajungi la n^2 tot nu va fi de ajuns. Eu am scos n * X. (unde n* X < n * n); Ca şi indiciu pentru n^2 :încearcă să scapi de acea funcţie palindrom; încearcă să verifici în o(1) dacă un şir e palindrom sau nu; apoi pt complexitatea n * X : când mergi cu j-ul înapoi (de la i-1 la 1) încearcă să faci cumva ca acel j să sară anumite poziţii despre care şti sigur că nu se poate afla un palindrom(folosindu-te de nişte informaţii de la paşii anteriori).
Spor !