1553 Caves and tunnels

[•Marius]

http://acm.timus.ru/problem.aspx?space=1&num=1553

Se poate mai bine de O(sqrt h) pe query si O(1) pe update ? h e inaltimea arborelui. Ideea mea a fost sa folosesc ideea determinarii LCAului in O(sqrt h).
Fiecare nod contine valoarea sa care se poate modifica la un update iar altele retin valoarea maxima dintre toate nodurile situate intre Level(x) + 1 si Level(x) + sqrt h. Pentru query merg in "sus" pana ajung la LCA, totul in 3 * sqrt h pasi.

[•Cosmin]

Poti sa faci log n pe update si log n pe query sau log^2 n pe query. Imparti arborele in lanturi cu heavy path decomposition: e o procedura recursiva ce gaseste un lant care porneste de la radacina arborelui si merge inspre fiul care e radacina unui subarbore cu numarul cel mai mare de noduri, dupa ce ai ajuns in o frunza, aplici procedura recursiv pe ceilalti arbori ramasi. Dupa ce ai impartit arborele in lanturi, pentru a merge pana in radacina dintr-un nod trebuie sa treci prin maxim log n lanturi diferite. Pe fiecare lant faci un range query. Asa rezolvi problema cu O(log^2 n) timp pe query, si parca daca folosesti biased finger trees iese O(log n) pe query.

[•domino]

Sigur poti face O(1) pe update la treaba cu sqrt() ?

[•Cosmin]

Un caz nasol ar fi un arbore stea cu o radacina si n - 1 fii. Daca faci update la radacina e clar ca trebuie sa faci update la mai mult de O(1) valori.

[•Marius]

Sigur poti face O(1) pe update la treaba cu sqrt() ?

Nu, nu e bine.

Nu gasesc nimic pe internet sa ma ajute sa inteleg heavy path decomposition. Rog pe oricine are ceva material sa mi-l ofere si mie.

[•domino]

Vezi www.cs.sunysb.edu/~bender/pub/latin02-level.ps , solutia <O(n), O(lg n)>. Acolo e longest path decomposition, dar e acelasi lucru pt heavy (daca nu ma insel, heavy inseamna sa alegi subarborele cu cel mai multe noduri la fiecare pas)

[•Marius]

Multumesc. Aproape am reusit. Un TLE pe la testul 25. Sa mearga mai repede cu long path (ladder) decat cu heavy path decomposition ?

[•Cosmin]

nu cred ca trebuie sa scrii diferit ... eventual da un paste la cod sa ma uit peste el si sa vedem ce poate fi imbunatatit.

[•Marius]

Nu mai e nevoie. Am reusit sa o scot in 1.1 s si 360 linii de cod.  Multumesc inca o data pentru ajutor.

[•domino]

Ai facut ceva special ca sa mearga asa repede?

[•Marius]

Doar am optimizat codul: am parsat citirea, iar pentru alocarea grafului si a arborilor de intervale pentru fiecare path am folosit zone dintr-un tablou "mare" declarat la inceputul programului. Pentru lca raspund in O(1) cu preprocesare in O(N log N).

[•mugurelionut]

O problema asemanatoare este http://www.spoj.pl/problems/QTREE/, de pe SPOJ, doar ca aici se schimba costul unei muchii, nu cel al unui nod. De curiozitate, heavy path decomposition e o tehnica cunoscuta prin comunitatea informaticienilor de pe la noi ?    Eu, personal, abia am "descoperit-o" acum vreo luna si un pic, pornind de la alte chestii [ conceptul de "path separator" ], dar mi se pare o idee foarte misto

[•domino]

O problema asemanatoare este http://www.spoj.pl/problems/QTREE/, de pe SPOJ, doar ca aici se schimba costul unei muchii, nu cel al unui nod. De curiozitate, heavy path decomposition e o tehnica cunoscuta prin comunitatea informaticienilor de pe la noi ?    Eu, personal, abia am "descoperit-o" acum vreo luna si un pic, pornind de la alte chestii [ conceptul de "path separator" ], dar mi se pare o idee foarte misto

Eu stiam de anul trecut de chestia asta de la Cosmin, si cred ca mai stiu cativa oameni de atunci.

[•Cosmin]

Hmm, eu stiam de astea de cand era discutia cu level ancestor pe lista lu Francu prin 2003 sau 2004. Ca atunci am citit tot ce am prins legat de asta, dar QTREE e prima problema pe care am aplicat treaba cu descompunerea arborelui.