Pagini: [1] 2   În jos
  Imprimă  
Ajutor Subiect: 132 Distante  (Citit de 12781 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
ditzone
Vizitator
« : Noiembrie 19, 2005, 16:06:25 »

Aici puteţi discuta despre problema Distante.
Memorat
sarabogdan
Strain
*

Karma: 4
Deconectat Deconectat

Mesaje: 40



Vezi Profilul
« Răspunde #1 : Noiembrie 19, 2005, 16:09:38 »

Ce librarie trebuie sa includ sa folosesc memset?
Memorat
bogdan2412
Echipa infoarena
Nu mai tace
*****

Karma: 410
Deconectat Deconectat

Mesaje: 951



Vezi Profilul
« Răspunde #2 : Noiembrie 19, 2005, 16:21:15 »

string.h
Memorat
sarabogdan
Strain
*

Karma: 4
Deconectat Deconectat

Mesaje: 40



Vezi Profilul
« Răspunde #3 : Noiembrie 19, 2005, 18:07:59 »

ms
Memorat
cristy
De-al casei
***

Karma: 2
Deconectat Deconectat

Mesaje: 136



Vezi Profilul
« 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
Vorbaret
****

Karma: 33
Deconectat Deconectat

Mesaje: 166



Vezi Profilul
« 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 ).   Thumb up
Memorat

Vlad Berteanu
cristy
De-al casei
***

Karma: 2
Deconectat Deconectat

Mesaje: 136



Vezi Profilul
« 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
Nu mai tace
*****

Karma: 232
Deconectat Deconectat

Mesaje: 929



Vezi Profilul
« 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=6
Deci algoritmul optim este O(N).
Memorat
cristy
De-al casei
***

Karma: 2
Deconectat Deconectat

Mesaje: 136



Vezi Profilul
« 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 Deconectat

Mesaje: 98



Vezi Profilul
« 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
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« 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. Wink
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
Nu mai tace
*****

Karma: 232
Deconectat Deconectat

Mesaje: 929



Vezi Profilul
« 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
Nu mai tace
*****

Karma: 144
Deconectat Deconectat

Mesaje: 434



Vezi Profilul
« 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 Tongue )
Memorat
bogdan2412
Echipa infoarena
Nu mai tace
*****

Karma: 410
Deconectat Deconectat

Mesaje: 951



Vezi Profilul
« 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 Smile

[Later edit: mdea am gasit si eu pe google lee's algorithm pentru infasuratori convexe Whistle ]
« 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 Smile
Memorat
PuMa
Strain


Karma: 3
Deconectat Deconectat

Mesaje: 12



Vezi Profilul
« Răspunde #17 : Mai 08, 2006, 12:10:02 »

Puteti sa-mi dati si mie niste teste la pb asta pls! Pe testele mele(facut de generator si rezolvate cu brute) imi merge dar evaluatoru imi da numai 0p.  Brick wall Brick wall Brick wall Brick wall
Memorat

Totul e relativ!
alex_damian
Strain


Karma: 2
Deconectat Deconectat

Mesaje: 24



Vezi Profilul
« Răspunde #18 : Februarie 05, 2007, 17:08:26 »

are ceva special testul 7 la problema asta??
Memorat
DITzoneC
Nu mai tace
*****

Karma: 301
Deconectat Deconectat

Mesaje: 962



Vezi Profilul
« 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 Deconectat

Mesaje: 24



Vezi Profilul
« Răspunde #20 : Februarie 05, 2007, 20:01:14 »

nu, nu faceam asta. 10x. Thumb up
Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« 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
Echipa infoarena
Nu mai tace
*****

Karma: 410
Deconectat Deconectat

Mesaje: 951



Vezi Profilul
« 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
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« 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
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #24 : Februarie 05, 2007, 21:31:33 »

 Brick wall Brick wall Brick wall Brick wall Brick wall yep your'e right. scuze probabil ca lipsa orelor de somn isi face efectul Very HappyFool
Memorat
Pagini: [1] 2   În sus
  Imprimă  
 
Schimbă forumul:  

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