infoarena

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.

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

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

Nu pai altfel nu ar mai fi fost raspunsul 10.


Da. Sunt diferite.

Parametrii x si y pot fi si egali?

DA

Eu la asta am facut LCA + memoizare, dar iese urat din timp. Banuiesc ca era LCA + dinamica, cum ati facut?

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

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

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 :D . Tot respectul !

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.