|
Titlul: 205 PScNv Scris de: ditzone din Martie 26, 2006, 18:34:59 Aici puteţi discuta despre problema PScNv (http://infoarena.ro/problema/pscnv).
Titlul: 205 PScNv Scris de: cristi8 din Martie 26, 2006, 21:23:45 cand apare articolul cu solutii la runda finala ?
pana atunci.. care imi zice si mie ideea care lua 100p ? Titlul: 205 PScNv Scris de: Mircea Pasoi din Martie 26, 2006, 21:46:08 In curand, suntem inca obositi dupa finala :) Vezi solutia de la problema "Car" pentru o idee de 100 de puncte.
Titlul: 205 PScNv Scris de: Andrei Savu din Martie 29, 2006, 10:36:30 BelmanFord pentru minimizarea raportului dintre costul drumului si lungimea drumului iar valoarea lui k este retinuta pe masura ce sunt relaxate costurile drumurilor.
Titlul: 205 PScNv Scris de: Cosmin Negruseri din Martie 29, 2006, 12:19:52 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.
Titlul: 205 PScNv Scris de: Gheorghe Cosmin din Martie 29, 2006, 16:21:31 nu cumva ultimul test, este un "pic" cam mare, n fiind mai mare ca 200 000?
Titlul: 205 PScNv Scris de: Cosmin Negruseri din Martie 29, 2006, 17:32:19 Da un refresh ....
Titlul: 205 PScNv Scris de: Andrei Savu din Martie 30, 2006, 23:18:38 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 ).
Titlul: 205 PScNv Scris de: Andrei Savu din Martie 31, 2006, 11:00:00 http://garaj.xhost.ro/olimp/pscnv.txt
Titlul: 205 PScNv Scris de: Valentin Stanciu din Martie 31, 2006, 11:17:13 Citat din mesajul lui: http://garaj.xhost.ro/olimp/pscnv.txt 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) Titlul: Raspuns: 205 PScNv Scris de: ditzone din Aprilie 03, 2006, 23:04:39 S-au modificat teste si sursele din arhiva sunt reevaluate....
Titlul: Răspuns: 205 PScNv Scris de: Andrei Homorodean din Septembrie 09, 2007, 23:19:42 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) Titlul: Răspuns: 205 PScNv Scris de: Ionescu Vlad din Noiembrie 05, 2007, 18:57:50 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:
Citat 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? Titlul: Răspuns: 205 PScNv Scris de: Adrian Diaconu din Noiembrie 05, 2007, 19:07:52 di 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 dy 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. Titlul: Răspuns: 205 PScNv Scris de: Ionescu Vlad din Noiembrie 06, 2007, 14:37:11 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? :oops: 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? Titlul: Răspuns: 205 PScNv Scris de: Mihai Calancea din Octombrie 28, 2010, 08:50:52 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.
|