ditzone
Vizitator
|
|
« : Noiembrie 19, 2005, 16:06:25 » |
|
Aici puteţi discuta despre problema Distante.
|
|
|
Memorat
|
|
|
|
•sarabogdan
Strain
Karma: 4
Deconectat
Mesaje: 40
|
|
« Răspunde #1 : Noiembrie 19, 2005, 16:09:38 » |
|
Ce librarie trebuie sa includ sa folosesc memset?
|
|
|
Memorat
|
|
|
|
•bogdan2412
|
|
« Răspunde #2 : Noiembrie 19, 2005, 16:21:15 » |
|
string.h
|
|
|
Memorat
|
|
|
|
•sarabogdan
Strain
Karma: 4
Deconectat
Mesaje: 40
|
|
« Răspunde #3 : Noiembrie 19, 2005, 18:07:59 » |
|
ms
|
|
|
Memorat
|
|
|
|
•cristy
|
|
« Răspunde #4 : Aprilie 10, 2006, 19:13:14 » |
|
la problema asta...am facut un Lee...din nodul sursa...si iau 60 de pct....TLE pe restu...e mai bun Dijkstra?...
|
|
|
Memorat
|
... lipsa de inspiratie ...
|
|
|
•vladcyb1
|
|
« Răspunde #5 : Aprilie 10, 2006, 19:21:56 » |
|
Nu prea cred ca ai facut lee pentru ca muchiile nu au cost 1...presupun ca ai facut Bellman-Ford care este N * M...Dijkstra este N^2 sau ( N + M ) Log N ( cu heapuri ).
|
|
|
Memorat
|
Vlad Berteanu
|
|
|
•cristy
|
|
« Răspunde #6 : Aprilie 10, 2006, 19:32:11 » |
|
dar..trebuie ca muchii sa aiba neaparat costul 1?...merge si fara sa fie 1...
|
|
|
Memorat
|
... lipsa de inspiratie ...
|
|
|
•filipb
|
|
« Răspunde #7 : Aprilie 10, 2006, 19:41:25 » |
|
Nu merge cu Lee / BFS ( = cautare in latime ). Algoritmi de acest gen functioneaza numai in cazul in care toate costurile sunt egale. Aici costurile muchiilor pot fi diferite, deci trebuie facut cu djikstra pentru a calcula drumurile minime explicit. Totusi tu trebuie sa vezi doar daca distantele sunt bune, deci nu trebuie sa faci djikstra, trebuie sa verifici daca vectorul indeplineste conditiile impuse in djikstra: http://info.devnet.ro/articole.php?page=art&art=74&artpage=6Deci algoritmul optim este O(N).
|
|
|
Memorat
|
|
|
|
•cristy
|
|
« Răspunde #8 : Aprilie 10, 2006, 21:55:29 » |
|
asa....deci....Dijkstra in N+M... la inceput pun sursa in lista...apoi verific pt toate nodurile adiacente, distantele...daca is mai bune...pun nodul in lista...si il "relaxez"?...
|
|
|
Memorat
|
... lipsa de inspiratie ...
|
|
|
•gogu
Client obisnuit
Karma: 42
Deconectat
Mesaje: 98
|
|
« Răspunde #9 : Aprilie 10, 2006, 22:42:07 » |
|
Nu prea ai cum sa faci Dijkstra in O(N+M). Solutia din articol nu mai face relaxari, decat verifica daca costurile date se pot obtine (daca se gaseste pentru fiecare nod x un alt nod y astfel incat c[y]+cost[y,x]=c[ x ]) si mai vede daca nu se pot imbunatatii costurile prin relaxare.
|
|
« Ultima modificare: Aprilie 10, 2006, 22:44:22 de către gogu »
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #10 : Aprilie 12, 2006, 16:21:18 » |
|
tie in problema nu ti se cere sa calculezi distantele, doar sa verifici daca sunt bune cele din fisierul de intrare. articolul cu solutii ar trebui sa te lamureasca.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
VladS
Vizitator
|
|
« Răspunde #11 : Aprilie 13, 2006, 11:58:45 » |
|
Nici eu nu cred ca ai cum sa rezolvi problema cu Lee pentru ca Lee face infasuratoare convexa.
|
|
|
Memorat
|
|
|
|
•filipb
|
|
« Răspunde #12 : Aprilie 13, 2006, 12:55:13 » |
|
? Esti sigur ca face asta?... Eu cred ca pentru infasuratoare convexa e Hill ( sau Graham ), nu Lee...
|
|
|
Memorat
|
|
|
|
•greco
|
|
« Răspunde #13 : Aprilie 13, 2006, 13:46:22 » |
|
Nu exista nici un algoritm Lee, decat in folclorul romanesc. Lee, asa cum il numim noi, reprezinta de fapt cautare in latime (BFS).
|
|
|
Memorat
|
Jump in the cockpit and start up the engines Remove all the wheelblocks there's no time to waste Gathering speed as we head down the runway Gotta get airborne before it's too late.
|
|
|
u-92
Vizitator
|
|
« Răspunde #14 : Aprilie 13, 2006, 15:11:31 » |
|
defapt exista algoritmul lui Lee, numai ca e ceva pt infasuratoare convexa cum zicea VladS mai sus (am gasit pe google )
|
|
|
Memorat
|
|
|
|
•bogdan2412
|
|
« Răspunde #15 : Aprilie 13, 2006, 15:29:36 » |
|
Dude, ala e Hill... si nici ala nu prea exista oficial sub denumirea asta.. doar in folcloru' romanesc [Later edit: mdea am gasit si eu pe google lee's algorithm pentru infasuratori convexe ]
|
|
« Ultima modificare: Aprilie 13, 2006, 15:38:01 de către bogdan2412 »
|
Memorat
|
|
|
|
ditzone
Vizitator
|
|
« Răspunde #16 : Aprilie 13, 2006, 15:32:57 » |
|
Eh .. sunt doar denumiri.. nu cred ca e asa important ... Oricum la problema asta nu e nevoie nici de Hill, nici de Lee
|
|
|
Memorat
|
|
|
|
•PuMa
Strain
Karma: 3
Deconectat
Mesaje: 12
|
|
« Răspunde #17 : Mai 08, 2006, 12:10:02 » |
|
|
|
|
Memorat
|
Totul e relativ!
|
|
|
•alex_damian
Strain
Karma: 2
Deconectat
Mesaje: 24
|
|
« Răspunde #18 : Februarie 05, 2007, 17:08:26 » |
|
are ceva special testul 7 la problema asta??
|
|
|
Memorat
|
|
|
|
•DITzoneC
|
|
« Răspunde #19 : Februarie 05, 2007, 19:11:49 » |
|
Ai verificat ca intr-adevar fiecare nod i se afla la distanta Di, adica exista o muchie (x,i) de cost c astfel incat Di=Dx+c ?
|
|
|
Memorat
|
|
|
|
•alex_damian
Strain
Karma: 2
Deconectat
Mesaje: 24
|
|
« Răspunde #20 : Februarie 05, 2007, 20:01:14 » |
|
nu, nu faceam asta. 10x.
|
|
|
Memorat
|
|
|
|
•devilkind
|
|
« Răspunde #21 : Februarie 05, 2007, 21:22:34 » |
|
hmm.. si totusi de ce e o(n)?? mie mi se pare o(n*m). Ptr fiecare nod verific toate muchiile care pleaca din el. sau am inteles eu gresit??
|
|
|
Memorat
|
|
|
|
•bogdan2412
|
|
« Răspunde #22 : Februarie 05, 2007, 21:26:44 » |
|
M e numarul total de muchii. Pentru un nod nu verifici toate cele m muchii existente, ci doar cele care pleaca din acel nod. Per total verifici N noduri si M muhcii. -> complexitate O(N + M)
|
|
|
Memorat
|
|
|
|
•Marius
|
|
« Răspunde #23 : Februarie 05, 2007, 21:27:04 » |
|
hmm.. si totusi de ce e o(n)?? mie mi se pare o(n*m). Ptr fiecare nod verific toate muchiile care pleaca din el. sau am inteles eu gresit??
Daca ai liste de adiacenta, atunci fiecare nod are grad[n] noduri in lista sa. Dar suma tuturor gradelor nodurilor e 2 * M, de unde complexitatea O(N + M).
|
|
|
Memorat
|
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
|
|
|
•devilkind
|
|
« Răspunde #24 : Februarie 05, 2007, 21:31:33 » |
|
|
|
|
Memorat
|
|
|
|
|