Titlul: 565 Pali Scris de: Adrian Diaconu din Noiembrie 19, 2007, 00:07:49 Aici puteţi discuta despre problema Pali (http://infoarena.ro/problema/pali).
Titlul: Răspuns: 565 Pali Scris de: Cosmin Negruseri din Iunie 20, 2008, 09:16:41 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.
Titlul: Răspuns: 565 Pali Scris de: Gabriel Bitis din Iunie 20, 2008, 11:22:29 Titlul: Răspuns: 565 Pali Scris de: Marius Stroe din Iunie 21, 2008, 12:56:39 Ce se poate, O(N) sau O(N lgN)?
Titlul: Răspuns: 565 Pali Scris de: Gabriel Bitis din Iunie 21, 2008, 18:29:58 :oops: e tot O(n^2)
Pentru un test in care sirul e format din elemente identice, are complexitate patratica. Titlul: Răspuns: 565 Pali Scris de: Parfene Narcis din Martie 25, 2009, 15:09:44 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? Titlul: Răspuns: 565 Pali Scris de: Mihai Calancea din Martie 25, 2009, 15:59:43 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. :)
Titlul: Răspuns: 565 Pali Scris de: Vlad Eugen Dornescu din Martie 14, 2010, 17:50:59 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 ? :o Stie cineva sa-mi raspunda ? Nu inteleg optimizarea asta... Haideti ma va rog... cum calculez intr-o matrice a
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 Titlul: Răspuns: 565 Pali Scris de: Dragos Oprica din Martie 15, 2010, 19:34:37 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 Titlul: Răspuns: 565 Pali Scris de: Simoiu Robert din Martie 15, 2010, 19:36:00 Pai a zis ca a citit-o dar nu stie ce scrie acolo si vrea sa-i explicati
Titlul: Răspuns: 565 Pali Scris de: Vlad Eugen Dornescu din Martie 15, 2010, 19:39:32 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 Titlul: Răspuns: 565 Pali Scris de: Andrei Grigorean din Martie 16, 2010, 11:24:59 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. Citat si de ce Pali[k+1][l-1]=1 in caz ca l-k>=2 ? :o 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. Titlul: Răspuns: 565 Pali Scris de: Vlad Eugen Dornescu din Martie 16, 2010, 14:39:47 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. Titlul: Răspuns: 565 Pali Scris de: Vasilut Lucian din Octombrie 28, 2012, 16:49:10 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. ](*,) Titlul: Răspuns: 565 Pali Scris de: Salajan Razvan din Octombrie 28, 2012, 17:13:34 Î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 ! |