205 PScNv

[ditzone]

Aici puteţi discuta despre problema PScNv.

[cristi8]

cand apare articolul cu solutii la runda finala ?
pana atunci.. care imi zice si mie ideea care lua 100p ?

[•domino]

In curand, suntem inca obositi dupa finala Vezi solutia de la problema "Car" pentru o idee de 100 de puncte.

[•andrei_savu]

BelmanFord pentru minimizarea raportului dintre costul drumului si lungimea drumului iar valoarea lui k este retinuta pe masura ce sunt relaxate costurile drumurilor.

[•Cosmin]

Andrei ai luat 100? Ca din ce vad ca ai scris aici vad ca nu prea ai inteles problema ... Bellman Ford aplicat normal ar fi trebuit sa ia 60-70p.

[•gcosmin]

nu cumva ultimul test, este un "pic" cam mare, n fiind mai mare ca 200 000?

[•Cosmin]

Da un refresh ....

[•andrei_savu]

Da, am luat 100 de puncte. Nu stiu cat de normal l-am implementat. O sa dau un link catre sursa dar pe moment am o problema cu sistemul de operare ( windows-ul a murit iar din linux nu pot sa accesez partitia ntfs, dar o rezolv curand ).

[•andrei_savu]

http://garaj.xhost.ro/olimp/pscnv.txt

[•svalentin]

Orice fisier gazduit de Xhost trebuie accesat prin intermediul unei paginii web vizibile, gazduita in acelasi cont Xhost.
You must supply a local referer to get this URL from this server (engl., approximativ)

[ditzone]

S-au modificat teste si sursele din arhiva sunt reevaluate....

[•peanutz]

E foarte enervanta prb. Testez si tot nu iasa. Imi da segmentation fault si sunt aproape sigur ca nu depasesc pentru ca am verificat sursa, si am si recitit enuntul pentru detalii.
Ma rog, unde ar putea fi cazuri speciale? Daca exista muchie de la un nod la el insasi, atunci pondera e k? Daca nu exista atunci e 0 sau infinit? Ceva sugestii? Eventual, un test mai tricky. Ma enerveaza faptu ca o problema, aparent simpla, imi da batai de cap. (Da, tin cont ca e multigraf)

[•Dastas]

Mi-ar putea explica cineva mai pe larg un pic solutia oficiala, cea cu dijkstra modificat? Un lucru pe care nu-l inteleg este urmatorul:

Cum ponderile muchiilor sunt numere de la 1 pana la 1000 inseamna ca in d[ i] oricare ar fi nodul i va fi intotdeauna mai mica sau egala cu 1000.

d[ i] ce reprezinta? Daca reprezinta distanta de la sursa pana la nodul i, atunci aceasta poate lua valori mai mari decat 1000... deci ce reprezinta de fapt?

Si inca ceva, listele astea cum se parcurg mai exact?

[•DITzoneC]

d_i este valoarea minima pentru care exista un drum de la x la i ce are toate muchiile mai mici sau egale cu costul respectiv (adica d_y va fi exact raspunsul pentru problema)

Listele se parcurg crescator intai cele cu cost 0, apoi cele cu cost 1, ...

Sper ca mi-am amintit bine problema.

[•Dastas]

Tot nu cred ca am inteles... fac in felul urmator si iau 0 puncte, desi pe exemplu merge:

Pentru liste am folosit STL vector.

La inceput setez d[ x] = 0 si il adaug pe x in L[0].

Apoi, pentru fiecare i de la 0 la 1000, parcurg lista L[ i] cu un j si daca i == d[ L[ i][j] ], expandez aceste noduri, adaugand vecinii lor in listele corespunzatoare. Daca pot reduce vreun d pentru vecini, o fac...

Ce n-am inteles? Banuiesc ca se poate intampla ca la un pas i, sa adaug un nod intr-o lista k < i, nod la care nu se va mai ajunge niciodata... atunci cum ar trebui sa procedez?

[•klamathix]

Eu n-am fost atent la enunt si am considerat graful neorientat, implementand solutia in Mlog*N cu multimi disjuncte. Mai ciudat e ca am luat 100 pe ea. Poate ar trebui modificate un test sau doua si grupate cu altele, ca sa crape solutiile de genul.