Pagini: 1 [2] 3   În jos
  Imprimă  
Ajutor Subiect: 257 Catun  (Citit de 32747 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
Tabara Mihai
Vizitator
« Răspunde #25 : Octombrie 07, 2006, 16:19:03 »

e gresit ce faci tu acolo la initializare.. for-ul ala de la 1 la k.. nu calculezi minimul pentru nodurile vecine fortaretelor

 Aha Aha

Ai avut dreptate. Applause
Am schimbat acolo si merge de 70 acuma.
Cred ca o sa incerc pe heap-uri pentru 100 Think ( desi nu prea le stapanesc  Whistle)

 Weightlift
Memorat
znakeu
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 3



Vezi Profilul
« Răspunde #26 : Mai 18, 2008, 12:13:40 »

Cred ca este o problema cu testul 1, am rezolvat prob parsand citirea si tot luam 90 pt luand WA pe testul 1. Acum am modificat citirea citind ca tot omul numar cu numar si vad ca iau 100. Cum parsarea nu e gresita.... banuiesc ca este ceva in neregula cu testul.
Memorat
DITzoneC
Nu mai tace
*****

Karma: 301
Deconectat Deconectat

Mesaje: 962



Vezi Profilul
« Răspunde #27 : Mai 18, 2008, 17:00:57 »

Ai dreptate. Era un '\n' pus aiurea prin fisier. Am modificat testul si am dat o re-evalare.
Memorat
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #28 : Octombrie 03, 2008, 20:35:29 »

Am si eu o intrebare... cum se poate scoate O(M log N) ca m-am tot chinuit si nu reusesc, in conditiile in care dijkstra de la un nod la toate celelalte se face in O(M log N), iar aici imi trebuie de la toate nodurile la toate cetatiile  Confused
Memorat
blasterz
Nu mai tace
*****

Karma: 92
Deconectat Deconectat

Mesaje: 255



Vezi Profilul
« Răspunde #29 : Octombrie 03, 2008, 20:46:13 »

Pai nu aplici dijkstra decat o singura data!

Bagi toate fortaretele in coada / heap si apoi ii dai bataie cu bellman-ford-ul / dijkstra pe heap Smile
Memorat
recviem
Client obisnuit
**

Karma: -26
Deconectat Deconectat

Mesaje: 62



Vezi Profilul
« Răspunde #30 : Octombrie 04, 2008, 12:45:31 »

In cazul asta la dijkstra poti folosi vectorul de tati pentru a pastra fortareata de care apartine fiecare catun, adica radacina din care pleaca drumul. Nu conteaza drumul in sine.

prima data stabilesc pt vecinii directi a celor k cetati : distanta si totodata sol[] ( care retine cetate ) si ii pun in heap
dupa care fac dijkstra si verific daca gasesc d[x->vf] > d + x->cost || actualizez d[] si sol[]
                                                      sau daca is egale verific dak sol ii mai mic decat sol[x->vf] si actualizez sol[]
km atat ...

poate te ajuta si asta.. sol[] e de fapt vectorul de tati.
Memorat
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #31 : Octombrie 05, 2008, 09:56:29 »

in prima faza nu prea intelesesem ce vroia sa zica in postu ala (pan' la urma am inteles), da' mi sa parut mult mai simplu bellman ford cu coada circulara, adica mi-a intrat fara probleme in timp la toate testele, chiar si fara optimizarea cu sirul de vizitate + ca dijkstra e mai lung (ca linii de cod) decat belman ford.
multzam la toti pt hinturi  Smile
Memorat
cosmin79
Strain
*

Karma: 36
Deconectat Deconectat

Mesaje: 46



Vezi Profilul
« Răspunde #32 : Octombrie 03, 2009, 23:17:01 »

Testele la problema asta sunt prost date. Am scos 100 pct : http://infoarena.ro/job_detail/353044 cu o sursa in care aveam complexitate O(n*m*k) cu cate un bellman ford pt fiecare oras de tip fortareata.  Ar fi bine daca ar putea cineva sa le mai schimbe.peacefingers
Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #33 : Octombrie 04, 2009, 00:37:17 »

De ce nu te implici chiar tu ca sa le schimbi? Nu e treaba grea si multi utilizatori iti vor multumi pentru efortul depus. In plus, esti cu un pas mai aproape de echipa infoarena.

Daca esti interesat, contacteaza-ma printr-un mesaj privat.
Memorat

Am zis Mr. Green
S7012MY
Nu mai tace
*****

Karma: 26
Deconectat Deconectat

Mesaje: 648



Vezi Profilul
« Răspunde #34 : Iunie 08, 2010, 14:17:07 »

poate cineva sa-mi dea un test mai mare?
Memorat
S7012MY
Nu mai tace
*****

Karma: 26
Deconectat Deconectat

Mesaje: 648



Vezi Profilul
« Răspunde #35 : Iunie 24, 2010, 11:29:33 »

La z nu sunt restrictii?
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« Răspunde #36 : Noiembrie 08, 2010, 19:05:08 »

Greseala pe care o faceam eu (cand luam 40) era ca nu updatam heap-ul in caz ca gaseam un nod deja introdus in heap care are distanta noua mai mica decat inainte. Poate scutesc pe cineva de niste ore pierdute si nervi Very Happy
Memorat
AnDrEwBoY
Strain
*

Karma: 4
Deconectat Deconectat

Mesaje: 36



Vezi Profilul
« Răspunde #37 : Noiembrie 10, 2010, 23:43:11 »

Iau doar 20 de puncte pe problema asta. Ce gresesc?

1. Imi adaug toate nodurile ce sunt fortarete intr-o coada.
2. Aplic Bellman-Ford.
3. Imi construiesc rezultatul in O(n*p), unde p e numarul de fortarete.

Stiu ca nu pasul trei strica tot dar nu am reusit sa ma prind cum fac toata treaba in real time. Smile
Memorat
freak93
Echipa infoarena
Nu mai tace
*****

Karma: 342
Deconectat Deconectat

Mesaje: 819



Vezi Profilul
« Răspunde #38 : Noiembrie 11, 2010, 02:45:14 »

Nu inteleg exact la ce te referi cand spui real-time, dar daca vrei o solutie in O(n) dupa BF, pur si simplu la BF mai tii o valoare pentru fiecare nod, anume foratareata de care apartine, la care evident ca poti da update in O(1) cand treci prin acel element in BF. In rest e buna ideea.
 Sper sa te ajute Very Happy
Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #39 : Noiembrie 11, 2010, 08:34:18 »

Adi: Ai grija ca lumea in general intelege parcurgere in latime prin BF, nu Bellman Ford.  Thumb up
Memorat

Am zis Mr. Green
freak93
Echipa infoarena
Nu mai tace
*****

Karma: 342
Deconectat Deconectat

Mesaje: 819



Vezi Profilul
« Răspunde #40 : Noiembrie 11, 2010, 15:02:22 »

O sa tin minte. Mie sincer imi intra in cap Bellman-ford la BF si Breadth-first-search la BFS. Ma voi adapta Smile
Memorat
Luffy
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #41 : Martie 11, 2011, 20:11:53 »

Aveti vreun exemplu de test? Nu inteleg de ce imi da raspuns gresit, pentru ca pana acum a trecut toate testele mele.  Confused Multumesc anticipat.
Memorat
psycho21r
Client obisnuit
**

Karma: -15
Deconectat Deconectat

Mesaje: 74



Vezi Profilul
« Răspunde #42 : Februarie 16, 2012, 23:12:58 »

Cred că e timpul să nu mai umplu evaluatorul de surse inutile și să cer puțin ajutor.

Mojoritatea surselor pe care le-am trimis dau bine pe testele mele, am folosit mai multe idei. Prima dată am încercat să fac dijkstra pentru fiecare fort și am luat 50 (folosind priority_queue), după am făcut dijkstra o singură dată, plecând cu toate forturile în priority_queue și am luat 40, după am încercat să fac dijkstra cu heap începând de la un nod în plus care face legătura între fortărețe, muchiile incidente cu el având costul 0, și am luat 20.

Unde tot greșesc în gândire?
Memorat
S7012MY
Nu mai tace
*****

Karma: 26
Deconectat Deconectat

Mesaje: 648



Vezi Profilul
« Răspunde #43 : Februarie 17, 2012, 00:02:17 »

Nu mai tin minte exact problema dar cred ca trebuie sa faci bellman ford. Eu am pornit cu toate fortaretele in coada. Sper sa te ajute Smile
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« Răspunde #44 : Februarie 17, 2012, 00:09:49 »

Merge si cu Dijkstra. Initializezi toate distantele cu infinit, apoi introduci fortaretele in heap si le setezi distanta la 0. Ai grija la implementare si ar trebui sa mearga.
Memorat
psycho21r
Client obisnuit
**

Karma: -15
Deconectat Deconectat

Mesaje: 74



Vezi Profilul
« Răspunde #45 : Februarie 17, 2012, 01:47:58 »

Știu că vă sâcâi, dar e vreun șmen mai aparte aici și nu mă prind eu? Înafară că fac dijkstra/bellman-ford și bag mai multe chestii în coadă de la început.

Eu updatez harta (vectorul) de fortărețe corespunzătoare de fiecare dată când găsesc un drum mai scurt, adică când lungimea drumului până la nodul curent + distanața dintre nodul curent și i < lungimea drumului până la i, atunci salvez și fort(i) = fort(nod curent). Iar fortărețele au inițial care fortărețe corespunzătoare pe ele însiși, ca și cum aș salva nodul precedent ca să reconstruiesc drumul, numai că salvez aceleași noduri mereu (fortărețele).

Mulțumesc anticipat și îmi pare rău dacă am folosit prost limba română, e cam târziu și îmi pică ochii de somn.
Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #46 : Februarie 17, 2012, 08:45:45 »

E bine.
Memorat

Am zis Mr. Green
thesilverhand13
Strain
*

Karma: 9
Deconectat Deconectat

Mesaje: 32



Vezi Profilul
« Răspunde #47 : Februarie 24, 2012, 01:04:20 »

Cred ca exemplul este gresit.In cerinta spune asa:
Citat
Daca un catun este la distanta egala de doua fortarete, se va considera ca apartine fortaretei cu numarul de identificare minim.
.

Iar in exemplu avem asa:
Citat

1 3 6
1 5 3
...
2 3 9

Atunci pentru a treia fortareata in exemplul dat mai sus nu ar trebuii sa arate 2?
Dupa capul meu, pana la catunul cu numarul 3 distanta de la castelele 2 si 5 sunt egale( 9 unitati de timp ).

L.E: nevermind,de fapt distanta de la castelul 5 este egala cu 7 unitati de timp,greseala mea  Whistle
« Ultima modificare: Februarie 24, 2012, 01:14:30 de către Florea Toma Eduard » Memorat
VisuianMihai
De-al casei
***

Karma: -9
Deconectat Deconectat

Mesaje: 121



Vezi Profilul
« Răspunde #48 : Iunie 22, 2012, 14:43:15 »

iau WA pe 5 teste si nu stiu unde gresesc. De fiecare data cand intalneam un castel, faceam un Dijkstra pornind de la castel, iar drumurile de la fortareata la sate le puneam intr-un vector pe care il actualizam tot timpul dupa ce intalneam castele.
Am facut si cazul cu indicele minim.
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« Răspunde #49 : Iunie 22, 2012, 16:41:36 »

Probabil nu gaseai greseala fiindca programul tau functioneaza doar cand fortaretile sunt date in ordine crescatoare. Ai doua solutii:
1) Ori faci cautarea in ordinea crescatoare a fortaretilor (http://infoarena.ro/job_detail/760691?action=view-source)
2) Ori corectezi depistarea indicelui minim (era inutila in cazul in care sunt in ordine crescatoare - intotdeauna gasesti indicele mai mic inaintea indicelui mai mare - si gresita in celalalt caz) (http://infoarena.ro/job_detail/760698?action=view-source)

Alte remarci:
Acel algoritm nu e Dijkstra, chiar daca tu l-ai numit asa.
Faceai lucruri inutile cum ar fi: "if(c[curent]!= INF)" - conditia e tot timpul adevarata; la tine vectorul minimum[] si c[] semnificau acelasi lucru.
Memorat
Pagini: 1 [2] 3   În sus
  Imprimă  
 
Schimbă forumul:  

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