•Marius
|
|
« Răspunde #75 : Ianuarie 29, 2010, 13:04:04 » |
|
Am facut Dijkstra clasic si am luat 40pct. Imi poate explica cineva ce ar trebui sa fac cu heap-ul? Ca nu reusesc sa ma prind Intuiesc ca avem nevoie de un min-heap la care sa tinem in varf dinstanta de la nodul sursa la cel mai apropiat nod, dar nu imi dau seama cum ar trebui manipulat. Multumesc anticipat ! Fiecare nod din heap poate fi considerat ca o pereche (x, d), unde „x” reprezintă un nod din graf care se găseşte la distanţa „d” faţă de nodul sursă. Algoritmul lui Dijkstra presupune să obţii de „n-1” ori cel mai apropiat nod de sursă. Astfel, în vârful heapului ai cel mai apropiat nod de nodul sursă, dacă ţii heapul pe baza distanţelor. Extragi această pereche din vârful heapului, operaţie pe care o înveţi din manual dacă nu o ştii, după care relaxezi fiecare vecin al nodului tocmai obţinut. Se va întâmpla să relaxezi doar nodurile care încă mai sunt în heap, deoarece restul au distanţa mai mică iar muchiile au costuri pozitive. Când relaxezi un nod, acesta urcă în heap cât timp are o distanţă mai mică decât părintele său. E posibil să ajungă în vârf astfel. Repeţi procedeul.
|
|
|
Memorat
|
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
|
|
|
•alexandru92
|
|
« Răspunde #76 : Ianuarie 29, 2010, 13:27:42 » |
|
Am facut Dijkstra clasic si am luat 40pct. Imi poate explica cineva ce ar trebui sa fac cu heap-ul? Ca nu reusesc sa ma prind Intuiesc ca avem nevoie de un min-heap la care sa tinem in varf dinstanta de la nodul sursa la cel mai apropiat nod, dar nu imi dau seama cum ar trebui manipulat. Multumesc anticipat ! Faci exact ca la problema Heap
|
|
|
Memorat
|
|
|
|
•popoiu.george
|
|
« Răspunde #77 : Ianuarie 29, 2010, 14:55:19 » |
|
Multumesc Marius si alexandru pentru raspunsuri, am inteles rezolvarea, dar cu toate acestea iau 90pct. (WA pe testul 1) Nu inteleg ce este gresit in sursa mea, desi am recitit-o de peste 10 ori. Daca aveti timp sa aruncati o privire si sa vedeti ce este gresit as fi recunoscator, deoarece ma "sacaie" ideea de 90pct la o problema ce am impresia ca i-am inteles rezolvarea. Sursa este comentata, asa ca nu ar trebui sa fie greu de inteles. http://infoarena.ro/job_detail/388169?action=view-source
|
|
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #78 : Ianuarie 29, 2010, 14:59:15 » |
|
Accesul la testele problemelor din arhiva educationala este liber. Poti sa-ti downloadezi testul si sa vezi ce nu iti merge.
|
|
|
Memorat
|
Am zis
|
|
|
•alexandru92
|
|
« Răspunde #79 : Ianuarie 29, 2010, 15:44:46 » |
|
Esti sigru ? Chiar acum am downladat testul si am rulat sursa ta. In loc sa afiseze 10 la penultima valoare, pune 14. Fa un debug
|
|
|
Memorat
|
|
|
|
•popoiu.george
|
|
« Răspunde #80 : Ianuarie 29, 2010, 16:19:45 » |
|
Am rezolvat, chiar era un bug, merci Alexandru !
|
|
|
Memorat
|
|
|
|
•arnold23
Strain
Karma: 0
Deconectat
Mesaje: 1
|
|
« Răspunde #81 : Februarie 23, 2010, 09:21:34 » |
|
cu priority queue poate cineva sa obtine 100p?
|
|
|
Memorat
|
|
|
|
|
|
•ooctav
Strain
Karma: -1
Deconectat
Mesaje: 15
|
|
« Răspunde #84 : Martie 20, 2010, 22:26:25 » |
|
cod :
while(h.size() && pas<=1LL*n*m)
ce inseamna 1LL ?
|
|
|
Memorat
|
|
|
|
•mathboy
|
|
« Răspunde #85 : Martie 20, 2010, 22:29:50 » |
|
Il pui pe 1 tip long long. E ca o conversie a inmultirii.
|
|
|
Memorat
|
|
|
|
•O_Neal
Strain
Karma: 0
Deconectat
Mesaje: 15
|
|
« Răspunde #86 : Martie 31, 2010, 14:49:12 » |
|
merge si bellman ford varianta primitiva fara coada si nimic relaxezi muchii pana nu mai poti si iei 100 ! ironia sortii
|
|
|
Memorat
|
|
|
|
•gabitzish1
|
|
« Răspunde #87 : Martie 31, 2010, 14:55:53 » |
|
Scopul problemei Algoritmul lui Dijkstra, e sa inveti algoritmul lui Dijkstra.
|
|
|
Memorat
|
|
|
|
•O_Neal
Strain
Karma: 0
Deconectat
Mesaje: 15
|
|
« Răspunde #88 : Martie 31, 2010, 15:47:31 » |
|
evident, am facut si eu cu multiset si am luat 80 si ma multumesc cu atat.. defapt nu inteleg de ce set-urile din STL iau mai putin adica de ce ar fi mai ineficiente, in fine, consider ca daca iei toate in considerare ( lungimea sursei, timpu necesar implementarii si rezultatele in sine ) atunci e mai bine la un concurs sa alegi sa implementezi cu STL pt ca e mai simplu si ai timp pt celelalte chestii sa zic asa, acuma depinde si asta, daca unu o implementat nush cate probleme cu heapuri facute manual, cred si eu ca nu o sa fol STL, dar pt altii optiunea e clara
|
|
|
Memorat
|
|
|
|
•alexandru92
|
|
« Răspunde #89 : Martie 31, 2010, 16:03:31 » |
|
Un lucru ce are putea cauza ineficienta ar fi OOP. Poti folosi make_heap, pop_heap, push_heap, pentru a gestiona un heap.
|
|
« Ultima modificare: Martie 31, 2010, 17:08:15 de către alexandru »
|
Memorat
|
|
|
|
•O_Neal
Strain
Karma: 0
Deconectat
Mesaje: 15
|
|
« Răspunde #90 : Martie 31, 2010, 17:41:02 » |
|
hm.. am facut folosind chestiile alea.. si am luat mai putin adica am luat TLE la mai multe si nu cred ca am facut io gresit ceva adica am transformat sursa cu multiseturi intr-una folosind chestiile de care ziceai tu nimic altceva, lasa ca e bine si 80 cu multiseturi
|
|
|
Memorat
|
|
|
|
•blasterz
|
|
« Răspunde #91 : Martie 31, 2010, 21:43:03 » |
|
Ineficienta vine de la faptul ca set/multiset sunt implementat folosind Red-Black Trees, iar acestia au o constanta mult mai mare decat cea a unui heap. Cu functiile alea push_heap / pop_heap ar trebui sa poti lua 100.
|
|
|
Memorat
|
|
|
|
•Cosmin1490
Strain
Karma: 1
Deconectat
Mesaje: 17
|
|
« Răspunde #92 : August 01, 2010, 18:54:49 » |
|
Am scris un Dijkstra normal, am luat 50 de puncte. Am incercat apoi un Dijkstra cu heapuri, iese din timp la ultimul test si iau 90, iar in final cu un bellman cu coada si acelasi rezultat, iese din timp la ultimul test. Probabil implementarea mea cu heapuri nu e optima. Poate cineva sa arunce o privire si sa-mi dea un sfat? [LE] Am inteles unde gresesc la bellman, eu inserez nodul chiar daca este deja in coada, dar la dijktra cu heapuri tot am intrebari.
|
|
« Ultima modificare: August 01, 2010, 19:21:41 de către Balan Radu Cosmin »
|
Memorat
|
|
|
|
•BitOne
Strain
Karma: -1
Deconectat
Mesaje: 45
|
|
« Răspunde #93 : August 01, 2010, 21:00:22 » |
|
Implementeaza push_down iterativ si apoi vezi ce se intampla
|
|
|
Memorat
|
|
|
|
•Cosmin1490
Strain
Karma: 1
Deconectat
Mesaje: 17
|
|
« Răspunde #94 : August 01, 2010, 23:03:35 » |
|
aha... am sa incerc... ma gandeam ca motivu pt care pierd ceva timp e ca.. in bellman folosesc coada in stl.. in loc sa o implementez eu... iar in ambele cazuri.. reprezentarea grafului sub forma de vectori in stl.. si ma gandesc ca poate.. o reprezentare dinamica cu liste de adiacenta ar fi mai rapida
|
|
|
Memorat
|
|
|
|
•dornescuvlad
|
|
« Răspunde #95 : August 02, 2010, 01:10:10 » |
|
Salut, m-am uitat eu peste sursa ta.Modificarea consta in faptul ca am folosit un vector<pair<int, int>> in loc de 2 vectori dinamici de dimensiune NMAX pentru a retine vecinii nodului, respectiv costul muchiei dintre acestia. Am observat ca la inceput calculai si un numar de aparitii, desi nu e nevoie. (Am sters si portiunea aia de cod) Uite sursa ta de 100 puncte : http://infoarena.ro/job_detail/474034?action=view-source
|
|
|
Memorat
|
|
|
|
•Cosmin1490
Strain
Karma: 1
Deconectat
Mesaje: 17
|
|
« Răspunde #96 : August 02, 2010, 11:32:21 » |
|
deci faptu ca retineam graful sub forma a doi vectori manca timpu.. si daca folosesc unul singur cu pair<> se rezolva.. multumesc mult pt timpu acordat [LE] si partea cu numarul de aparitii pe care ai mentionat-o , din cate stiu n-am folosit nimic de genul acesta ... dar oricum.. acea modificare.. din 2 vectori cu unu pair... a rezolvat problema:D multumesc [LE].. ahh am inteles . dar acea chestie care zici ca numara aparitiile era folosit p postul de un vector true false, desi era declarat int... era ceva memorie irosita ce-i drept.. dar l-am schimbat in unul bool
|
|
« Ultima modificare: August 02, 2010, 11:52:13 de către Balan Radu Cosmin »
|
Memorat
|
|
|
|
•cosmyo
Strain
Karma: 1
Deconectat
Mesaje: 14
|
|
« Răspunde #97 : Septembrie 01, 2010, 21:38:06 » |
|
Eu nu inteleg cum se ia 90 de pct cu 2 vectori separati din stl,iar cu un vector de pair<long,long> se ia 100.
|
|
|
Memorat
|
|
|
|
•Cosmin1490
Strain
Karma: 1
Deconectat
Mesaje: 17
|
|
« Răspunde #98 : Septembrie 08, 2010, 16:48:00 » |
|
atunci cand tii unul pair faci o singura inserare pe muchie si nu doua ma gandesc eu.
|
|
|
Memorat
|
|
|
|
|
|