|
Titlul: 1984 Navigation Nightmare Scris de: Bogdan-Alexandru Stoica din August 20, 2007, 13:38:46 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? Titlul: Răspuns: 1984 Navigation Nightmare si 1987 Distance Statistics Scris de: Mircea Pasoi din August 21, 2007, 00:32:32 Cred ca ar trebui sa faci doua topic-uri, nu e bine sa discuti probleme la gramada.
Titlul: Răspuns: 1984 Navigation Nightmare Scris de: Bogdan-Alexandru Stoica din August 21, 2007, 09:28:52 ok, s-a rezolvat. :D
Titlul: Răspuns: 1984 Navigation Nightmare Scris de: Silviu-Ionut Ganceanu din August 21, 2007, 23:17:28 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 :) Titlul: Răspuns: 1984 Navigation Nightmare Scris de: Mircea Pasoi din August 21, 2007, 23:35:37 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).
Titlul: Răspuns: 1984 Navigation Nightmare Scris de: Bogdan-Alexandru Stoica din August 22, 2007, 11:11:47 pentru Silviu: chiar acum am Cormen-ul in fata. incep sa caut... :-k
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) Titlul: Răspuns: 1984 Navigation Nightmare Scris de: Silviu-Ionut Ganceanu din August 22, 2007, 20:43:00 Eu parca tin minte ca cu smenu ala din Cormen a mers uns :) Sper sa nu ma insel totusi :-k
Titlul: Răspuns: 1984 Navigation Nightmare Scris de: Airinei Adrian din August 24, 2007, 13:52:37 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]) |