Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 1984 Navigation Nightmare  (Citit de 11084 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
fireatmyself
Nu mai tace
*****

Karma: 35
Deconectat Deconectat

Mesaje: 492



Vezi Profilul
« : 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.  Brick wall Aveti vreo idee?
« Ultima modificare: August 21, 2007, 09:28:36 de către Bogdan A. Stoica » Memorat

Viata e scurta. Daca nu o putem lungi, macar s-o facem lata.
domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« Răspunde #1 : August 21, 2007, 00:32:32 »

Cred ca ar trebui sa faci doua topic-uri, nu e bine sa discuti probleme la gramada.
Memorat
fireatmyself
Nu mai tace
*****

Karma: 35
Deconectat Deconectat

Mesaje: 492



Vezi Profilul
« Răspunde #2 : August 21, 2007, 09:28:52 »

ok, s-a rezolvat.  Very Happy
Memorat

Viata e scurta. Daca nu o putem lungi, macar s-o facem lata.
silviug
Echipa infoarena
Nu mai tace
*****

Karma: 193
Deconectat Deconectat

Mesaje: 485



Vezi Profilul
« Răspunde #3 : 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 Smile
Memorat

"Don't gain the world and lose your soul, wisdom is better than silver or gold." [Bob Marley - Jamaican reggae musician & singer (1945 - 1981)]
domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« Răspunde #4 : 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).
Memorat
fireatmyself
Nu mai tace
*****

Karma: 35
Deconectat Deconectat

Mesaje: 492



Vezi Profilul
« Răspunde #5 : August 22, 2007, 11:11:47 »

pentru Silviu: chiar acum am Cormen-ul in fata. incep sa caut...  Think
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)
« Ultima modificare: August 24, 2007, 14:08:42 de către Bogdan A. Stoica » Memorat

Viata e scurta. Daca nu o putem lungi, macar s-o facem lata.
silviug
Echipa infoarena
Nu mai tace
*****

Karma: 193
Deconectat Deconectat

Mesaje: 485



Vezi Profilul
« Răspunde #6 : August 22, 2007, 20:43:00 »

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

"Don't gain the world and lose your soul, wisdom is better than silver or gold." [Bob Marley - Jamaican reggae musician & singer (1945 - 1981)]
astronomy
Nu mai tace
*****

Karma: 204
Deconectat Deconectat

Mesaje: 492



Vezi Profilul
« Răspunde #7 : 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])
« Ultima modificare: August 25, 2007, 10:20:35 de către Airinei Adrian » Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

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