1984 Navigation Nightmare

[•fireatmyself]

http://acm.pku.edu.cn/JudgeOnline/problem?id=1984

Ma chinui de ceva vreme la acesta problema si nu am reusit sa scot ceva ce sa intre in timp.  Aveti vreo idee?

[•domino]

Cred ca ar trebui sa faci doua topic-uri, nu e bine sa discuti probleme la gramada.

[•fireatmyself]

ok, s-a rezolvat. 

[•silviug]

Asta e clasica:

1. Ca sa vezi daca doua ferme sunt conectate folosesti multimi disjuncte.
2. Trebuie sa faci o structura care suporta LCA dinamic ca sa calculezi distantele. Asta se face cu ceva multimi disjuncte modificate, e destul de complicat.

SAU

2'. Este un algoritm de calculat LCA-uri offline prin Cormen. E simplu de codat si merge de minune pentru ca stii cand iti vin query-uri.
Uita-te pe la structuri de date, nu mai tin minte pe unde e si nici nu am cartea cu mine in Elvetia

[•domino]

O solutie bruta ar fi la fiecare pas cand reunesti doi subarbori sa recalculezi informatiile necesare pentru LCA (stramosi puteri ale lui 2). Daca la fiecare pas recalculezi doar pentru subarborele mai mic atunci complexitatea finala e O(N*lg N).

[•fireatmyself]

pentru Silviu: chiar acum am Cormen-ul in fata. incep sa caut... 
pentru Mircea: am incerca sa fac ce ai zis tu la o problema asemanatoare, numai ca atunci cand trebuia sa aflu LCA-ul, faceam smenul cu parcurgerea euler+RMQ. din pacate imi cam iese din memorie. tu, banuiesc, ca te folosesti doar de matricea aia cu stramosi (puteri ale lui 2).

Multumesc mult. Sper sa iau AC in cele din urma.

L.E. : scarbosenia problemei vine din faptul ca vrea distanta Manhattan intre doua noduri, fapt ce face dubioasa mentinerea distantelor in acea matrice (trebuie sa fixezi un sens de mers ca sa aduni distantele, spre exemplu inainte si sus sunt cu +, iar pe sensul invers sa scazi)

[•silviug]

Eu parca tin minte ca cu smenu ala din Cormen a mers uns Sper sa nu ma insel totusi

[•astronomy]

Cel mai simplu poti sa faci o parcurgere din nodul 1 si sa obtii d1[ i ] = distanta pe Ox pana la nodul i, d2[ i ] = distanta pe Oy pana la nodul i. Acum parcurgi instructiunile in ordine si faci cu multimi disjuncte, daca x si y sunt in aceiasi componenta distanta dintre ele este

Cod:

abs(d1[x]-d1[y])+abs(d2[x]-d2[y])