Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Arbpal  (Citit de 3666 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
eudanip
Echipa infoarena
Nu mai tace
*****

Karma: 307
Deconectat Deconectat

Mesaje: 695



Vezi Profilul
« : Martie 10, 2013, 13:54:51 »

Aici se pot pune întrebări legate de problema Arbpal de la Runda 3 a concursului .com 2012

Timpul alocat întrebărilor este de 1 ora dupa inceperea concursului. Întrebările vor fi formulate astfel încât să se poată răspunde cu DA sau NU. În caz contrar sau în cazul în care întrebarea își găsește răspuns în enunțul problemei, răspunsul va fi FARA COMENTARII.
Memorat
romircea2010
Strain
*

Karma: 18
Deconectat Deconectat

Mesaje: 35



Vezi Profilul
« Răspunde #1 : Martie 10, 2013, 14:38:02 »

In exemplu caracterul din nodul 1 nu trebuia sa fie 'a'?
Memorat
Cristy94
De-al casei
***

Karma: 37
Deconectat Deconectat

Mesaje: 128



Vezi Profilul
« Răspunde #2 : Martie 10, 2013, 14:43:22 »

P(x,y) si P(y,x) sunt considerate doua perechi diferite?
Memorat
eudanip
Echipa infoarena
Nu mai tace
*****

Karma: 307
Deconectat Deconectat

Mesaje: 695



Vezi Profilul
« Răspunde #3 : Martie 10, 2013, 14:44:53 »

In exemplu caracterul din nodul 1 nu trebuia sa fie 'a'?

Nu pai altfel nu ar mai fi fost raspunsul 10.

P(x,y) si P(y,x) sunt considerate doua perechi diferite?

Da. Sunt diferite.
Memorat
romircea2010
Strain
*

Karma: 18
Deconectat Deconectat

Mesaje: 35



Vezi Profilul
« Răspunde #4 : Martie 10, 2013, 14:49:25 »

Parametrii x si y pot fi si egali?
Memorat
edp100
Strain


Karma: 1
Deconectat Deconectat

Mesaje: 21



Vezi Profilul
« Răspunde #5 : Martie 10, 2013, 14:52:44 »

Parametrii x si y pot fi si egali?
DA
Memorat
Cristy94
De-al casei
***

Karma: 37
Deconectat Deconectat

Mesaje: 128



Vezi Profilul
« Răspunde #6 : Martie 10, 2013, 19:29:39 »

Eu la asta am facut LCA + memoizare, dar iese urat din timp. Banuiesc ca era LCA + dinamica, cum ati facut?
Memorat
tzipleatud
De-al casei
***

Karma: 104
Deconectat Deconectat

Mesaje: 117



Vezi Profilul
« Răspunde #7 : Martie 10, 2013, 19:34:13 »

Eu am facut un DF din fiecare nod S si calculam pentru fiecare nod i hash-ul stringului ce reprezinta lantul S->i si i->S. Daca cele 2 hash-uri erau egale, atunci aveam un palindrom. Problema era ca luam TLE caci faceam operatii modulo. Asa ca mi-am precalculat operatiile de modulo, si, ca prin minune, nu am scapat de TLE Smile .
Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #8 : Martie 10, 2013, 19:38:10 »

Eu am facut un fel de dinamica pe arbore. Ideea de baza era ca P(x,y) este palindrom daca P(tata[ x ],tata[ y ]) este palindrom si c[ x ]=c[ y ], insa trebuia sa tratezi cazuri particulare(cand nodurile sunt in acelasi subarbore, cel determinat de nodul de pe nivelul mai mic).  Very Happy
Memorat
alex_unix
Strain
*

Karma: 22
Deconectat Deconectat

Mesaje: 46



Vezi Profilul
« Răspunde #9 : Martie 10, 2013, 20:14:56 »

Chiar daca nu i-am dat de capat, mi se pare cea mai faina problema pe care am intalnit-o pana acum la vreun concurs Very Happy . Tot respectul !
Memorat
eudanip
Echipa infoarena
Nu mai tace
*****

Karma: 307
Deconectat Deconectat

Mesaje: 695



Vezi Profilul
« Răspunde #10 : Martie 11, 2013, 11:51:24 »

Initial solutia era asa: din fiecare nod pornim un dfs (presupunem ca e centru palindromului) si construim trie-ul arborelui (sau tinem hash). Din pacate si cu trie si cu hash merge mai prost ca sursa mea de O(n^3 cu kill), desi daca te chinui mult iti intra in timp si cu hash. Solutia oficiala este: ganditiva la d[ i ][ j ] = 0/1 daca lantul de la i la j este palindrom. Da nu tinem dinamica si pur si simplu dintr-un palindrom ne extindem in altu cu un dfs. Asta este O(numarul de solutii) care e maxim N^2.
« Ultima modificare: Martie 11, 2013, 11:58:00 de către Eugenie Daniel Posdarascu » Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

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