infoarena

Aici puteţi discuta despre problema Catun (http://infoarena.ro/problema/catun).

Care este complexitatea la aceasta problema? am un O(n^2), dijkstra pe liste....

Djikstra merge si O(M log N)...

Exista drumuri de lungime 0?

Toate costurile pe muchii sunt > 0.

of chiar nu inteleg dc scot numai 40 de pcte ... restu WA  :oops:
toate testele care le dau imi merg ( )

pai zi cum faci, eu iau 50 pct si nici eu nu inteleg ce e gresit.

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 ...

In teste exista muchii cu lungimi mai mari decat 1024. Aveti grija daca folositi restrictiile asupra lungimilor muchiilor in algoritmul de rezolvare. Asta pana cand vom reface testele  :-'

nu cre k ii de la asta pt k am obtinut 60 de pcte cu un program n*m care nu folosea long long ...

pai pune long long poate iei 100

nu mere  :angry:  sa fie de la implementare? sau nu ii buna ideea?

E buna ideea. Eu nu am folosit deloc long long.

Eu iau 80 de puncte cu si fara long long. Pe testele 3 si 8 iau WA. Any ideas why?

 \:D/ 100 dupa lungi chinuri ... greseam la refacerea heapului  :oops:

NU iau numai 10 puncte. :oops: :oops: :oops:

Am facut Dijkstra pe liste.Cu long long iau 0, iar cu long 10.
NU ma astept sa iau 100 cu Dijkstra pe liste, insa nici chiar 10 :'(.


Imi iese testul 7 corect.In rest TLE pe 3 teste si WA pe 6 teste.

Help pls. ](*,)

[Later Edit] => Mie mi s-ar parea normal sa imi iasa cu Dijkstra pe liste testele pe care am WA...nu?

Ai avut grija pentru fiecare nod sa retii raspunsul cel mai mic?

Da... :ok:


unde Inf(long int, long int) e functia care stabileste numarul de ordine minim.

 ](*,)

nush dak am inteles eu bine codu tau, dar am impresia ca verifici faci dinre un costul initial si costul vecinilor. la costul vecinilor ar trebui sa aduni si costul muchiei de la vecin la nod. 

PS: eu am luat 100 cu djikstra pe liste

100 cu O(N^2) ?  ???

dap, bine ca oricum am implementat apoi n log n insa luasem 100 si cu n^2

\:D/ Eu nu am putut sa iau mai mult de 70 de puncte cu un algoritm patratic... :thumbup:

Uite cam asa arata Dijkstra-ul meu

unde f[] tine sirul fortaretelor, Inf e functia care compara numarul de ordine a doua feude, iar sol e vectorul de iesire.

ce ii Inf ?? scrie ce face Inf :P

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. =D>
Am schimbat acolo si merge de 70 acuma.
Cred ca o sa incerc pe heap-uri pentru 100 :-k ( desi nu prea le stapanesc  :-')

 :weightlift:

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.

Ai dreptate. Era un '\n' pus aiurea prin fisier. Am modificat testul si am dat o re-evalare.

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  :?

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 :)

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.


poate te ajuta si asta.. sol[] e de fapt vectorul de tati.

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  :)

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:

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.

poate cineva sa-mi dea un test mai mare?

La z nu sunt restrictii?

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 :D

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. :)

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 :D

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

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

Aveti vreun exemplu de test? Nu inteleg de ce imi da raspuns gresit, pentru ca pana acum a trecut toate testele mele.  :? Multumesc anticipat.

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?

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 :)

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.

Ș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.

E bine.

Cred ca exemplul este gresit.In cerinta spune asa:
.

Iar in exemplu avem asa:

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  :-'

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.

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.

Da, am sortat fortaretele si am luat 100. Era gresita verificarea minimului cred. Mersi pt sfat :D

Imi poate spune si mie cineva ce gresesc e iau 10p?

Din cate mi se pare, gresesti in functia init.

Tu acolo iei vecinii fiecarei fortarete si le bagi distanta fata de cea mai apropiata fortareata, alaturi de indicele acestei fortarete.
Problema este ca tu vei face overwrite pe vectorul fort.

Sa presupunem ca ai fort = {1, 3, 4} cu indexare de la 1 si muchie de la 1 la 2 de cost 3 sa zicem.
Vei seta fort[2] = 1, iar astfel fort = {1, 1, 4}. Tu nu vei mai extinde fortareata 3.

Bafta!  :thumbup:

Am gasit problemele...mersi de ajutor

Iau 40 de puncte cu WA pe restul, si nu gasesc greseala nicidecum. Ma ajuta si pe mine cineva? :-s

@swim406
ai putea incepe prin a spune ce faci :)

Prima data am facut cate un dijkstra cu heap de la fiecare fortareata si am luat 70 ( TLE ). Apoi am facut o singura data dijkstra introducand in heap fortaretele si iau 30 ( WA ). Imi puteti spune va rog unde gresesc la varianta cu un dijkstra ?

Nu cred ca iei in considerare asta.

Am sortat fortaretele. Facand asta nu selecteaza automat fortareata cu numarul minim?

Nu.

Am rezolvat-o. Multumesc mult!

Rezolvat  :ok:

Imi poate da cineva testul 5?  :-'

Putin ajutor??
http://www.infoarena.ro/job_detail/1562827
Folosesc Heap, si Dijkstra o singura data, plecand de la valori nule pentru fortarete.

Scrie cod ingrijit daca vrei sa ti-l citeasca cineva.

Am sters comentariile si am aranjat parantezele...mai e ceva?

Am incercat si eu o implementare la pb asta, si am facut cate un dijkstra pentru fiecare catun, sa vad cea mai apropiata fortareata, dar imi iau un tle pe 5 teste. Any help?

http://www.infoarena.ro/job_detail/1736420

Ceea ce faci e mai mult Bellman-Ford decat Dijkstra.Oricum,asta nu e neparat relevant.O ideea ar fi sa nu pornesti de la fiecare catun spre fortarete ci sa incepi cu fortaretele.Iti tii un vector de fortarete si unul de costuri.In vectorul de fortarete tii fortareata cea mai apropiata si in cel de distante distanta pana la ea.Initializezi distantele la toate fortaretele cu 0,iar fortareata cea mai apropiata de fiecare o setezi ca ea insasi(evident).Cand actualizezi distanta minima la un nod,actualizezi si fortareata cea mai apropiata care este evident,fortareata cea mai apropiata a nodului care il preceda pe nodul curent in drumul minim spre o fortareata.La final,afisezi vectorul de fortarete,iar pentru elementele care stii ca sunt fortarete,afisezi 0.Ideea e ca si la un Dijkstra/Bellman-Ford clasic,dar in loc sa incepi de la un nod,incepi de la mai multe,punandu-le pe toate in coada/heap initial,iar apoi actualizezi inca un detaliu pe langa distanta.
Sper ca am fost de ajutor.

Gata, mersi fain, am facut sursa de 100p.

Cat despre confuzia mea dintre bell/dijkstra, cand am incercat prima oara sa invat dijkstra am gasit numai surse cu bell la problema de pe infoarena si am crezut ca aia e. Mai tarziu cand am invatat bell am observat ca sursele erau foarte similare intre ele si nu stiam care-i care. My bad..

Sal .
Testele de la problema asta sunt scrise prost pt java care aparent e ceva mai lent decat c++ ul .
Literalmente acelasi program ia numai 60 pct scris in java si 100 fara probleme scris in c++ .

Nu testele sunt de vina. Limita de timp de la problema nu este adaptata pentru Java.

putin ajutor va rog

http://www.infoarena.ro/job_detail/2004956?action=view-source

nu inteleg de ce iau WA pe 5 teste. Fac Dijkstra punand toate fortaretele in heap la inceput, mentinand 2 arrayuri pt distante si fortarete. Am verificat si conditia pt catun minim.

In teste n <= 32000
 :banana:

Eu am niste probleme cu testul 7. Primesc 90 puncet dar testul 7 nu vrea sa reuseasca.  ](*,)