|
Titlul: 102 Lanterna Scris de: Mircea Pasoi din Septembrie 04, 2005, 01:22:08 Aici puteţi discuta despre problema Lanterna (http://infoarena.ro/problema/lanterna).
Titlul: 102 Lanterna Scris de: Rus Cristian din Septembrie 17, 2005, 09:40:56 Dar pentru urmatorul set de date ce trebuie sa dea?
Cod: 4 5 0 0 0 0 4 1 2 2 1 1 3 1 1 2 4 3 2 3 4 5 1 Titlul: 102 Lanterna Scris de: Bogdan-Cristian Tataroiu din Septembrie 17, 2005, 11:30:11 5 3
Titlul: 102 Lanterna Scris de: Rus Cristian din Septembrie 17, 2005, 15:43:13 ms bogdan... va rog mai dati niste exemple...ca nu stiu unde am putut gresi...am 50 de pct...si...nu gasesc gresala, am wa pe restu... timpul e 0.01 s...si...cum faci generator de teste la o problema ca asta?..asa..simplu?...sau e un algoritm mai complicat?...ca sa iasa solutia din prima?...adica...sa iasa graf dinasta...
Titlul: 102 Lanterna Scris de: Iorgulescu Calin din Septembrie 26, 2005, 21:03:36 Am si eu o nelamurire la problema asta. Mi-se pare un pic ambiguu textul ei. Acolo spune ceva de genul: "daca alege o lanterna cu un nr. de wati mai mic decat necesar durata va fi strict mai mare... daca nu va fi mai mare sau egal". Adica el poate merge pe o zona chiar si fara lanterna dar ar dura mai mult? Sau cum? Cum influenteaza timpul de deplasare lanterna? Puteti sa incercati sa imi explicati si mie? :-k Mersi!
Titlul: 102 Lanterna Scris de: Bogdan-Cristian Tataroiu din Septembrie 27, 2005, 13:47:40 Ideea e sa afli timpu minim de deplasare si lanterna cu cel mai mic nr de wati astfel incat el sa poata sa se deplaseze de la baza 1 la baza n in acel timp minim. Nu se poate deplasa fara lanterna pe nici un drum.
Titlul: 102 Lanterna Scris de: Rus Cristian din Septembrie 27, 2005, 17:28:29 deci...daca sunt 2 drumuri, unu de lungime 20 si 20 de wati...si unu de lungime 10, si 30 de wati...si sunt 20 de tipuri de lanterna...atunci merge pe primu drum...nu pe al doilea..asa-i?
Titlul: 102 Lanterna Scris de: Bogdan-Cristian Tataroiu din Septembrie 27, 2005, 17:32:06 Daca sunt doar 20 lanterne merge pe ala de lungime 20. Daca ar avea 30 sau mai multe lanterne atunci ar merge pe cel de lungime 10
Titlul: 102 Lanterna Scris de: Mircea Pasoi din Noiembrie 07, 2005, 00:15:40 Am schimbat un test cu unul mai "provocator" si am reevaluat problema. (In caz ca va intrebati de ce unii au cu 10p mai putin decat inainte). :pimp:
Titlul: 102 Lanterna Scris de: Iorgulescu Calin din Noiembrie 22, 2005, 22:59:01 =D> =D> =D>
Recunosc ca este cu adevarat provocator. Dar cu toate astea...ati putea sa-mi dati macar un mic hint? Adica m-am tot chinuit si n-am reusit sa-l iau... :oops: Raman etern recunoscator pentru orice hint. [-o< Titlul: 102 Lanterna Scris de: cristi8 din Noiembrie 23, 2005, 01:53:46 ce se ia acum ? WA sau TLE ?
..eu vad ca am tot 100 si mai vroiam sa fac o mare optimizare inainte sa trimit, si am fost uimit ca am luat 100 ca mi se parea ceva neoptim :( eu vream 90 sa trebuiasca sa implementez si feature-ul meu :P [EDIT]: am implementat de curiozitate ce vroiam eu (sa nu ma mai intorc in tatal unui nod in bellman-ford, ca nu are cum sa conduca la rezultat).. si vad ca timpii orientativi sunt mai mari decat inainte.. ..eu nu inteleg de ce.. cineva intelege de ce ? PS: am vazut ca restul au WA pe testul 9, nu timp depasit Titlul: 102 Lanterna Scris de: Iorgulescu Calin din Noiembrie 23, 2005, 22:07:53 Algoritmul meu are o complexitate O(N^2*K). Adica... mai simplu... pt. fiecare K calculez drumul minim prin care se poate ajunge de la 1 la N, respectand conditia watilor. Algoritmul folosit e Dijkstra. Testul asta are ceva ce ar putea sa fie ratat?
Titlul: 102 Lanterna Scris de: cristi8 din Noiembrie 23, 2005, 22:43:42 pai nu poti sa faci dijkstra in o(n^2) pentru a gasi drumul minim de la 1 la n avand W wati.
o "stare" e caracterizata de un nod, distanta parcursa pana la el, dar si de numarul de wati pe care ii mai are in lanterna in nodul respectiv. Titlul: 102 Lanterna Scris de: Tiberiu-Lucian Florea din Noiembrie 23, 2005, 23:56:18 Atentie ca o mic nu e tot una cu O mare. :)
Titlul: 102 Lanterna Scris de: Iorgulescu Calin din Noiembrie 24, 2005, 14:44:23 Sunt constient ca este o stare. Astfel ca in Dijkstra pe langa un vector D cu proprietatea ca D=distanta minima de la 1 la i, mai tin si un vector D2=cati wati am consumat pana in i. Cand i este prieten am grija ca toate drumurile la care ajung prin i sa aiba numarul de wati resetat. Si asta fac pentru un l de la 1 la K. Si practic singura conditie de continuare este ca numarul de wati folositi pentru a ajunge intr-un nod j este mai mic decat l. Adica nu aleg un nod decat daca am wati sa ajung pana la el. Apoi retin drumul minim aflat din punct de vedere al timpului. Apoi dintre acestea retin pe cel pentru care am folosit cei mai putini wati. Iar spre rusinea mea :oops: care este diferenta intre o si O ? Mersi mult!
Titlul: 102 Lanterna Scris de: Ionel Corneliu Gog din Noiembrie 24, 2005, 15:02:02 Definim f(n)=O(g(n)) si f(n)=o(g(n)).
Pentru O - 0<=f(n)<=c*g(n) pentru o anumita constanta c>0. Pentru o - 0<=f(n)<=c*g(n) pentru toate constantele c>0. Titlul: 102 Lanterna Scris de: Iorgulescu Calin din Noiembrie 24, 2005, 15:35:04 Mersi... Util de stiut! =D> Dar totusi in legatura cu algoritmul meu... are cineva vreo/vreun sugestie/critica/sfat?
Titlul: 102 Lanterna Scris de: Andrei Grigorean din Noiembrie 24, 2005, 16:14:44 vezi ce face programu tau ptr:
Cod: 4 3 0 0 0 0 4 1 3 2 10 1 2 3 1 2 3 4 1 3 4 3 1 Titlul: 102 Lanterna Scris de: Marius Stroe din Februarie 10, 2006, 11:27:12 Ideea lui Calinux am avut-o si eu... dar ce da cu Dijkstra pentru:
Cod: 8 6 0 0 0 0 0 0 0 0 8 1 2 1 2 2 3 1 2 3 4 1 2 4 8 1 1 1 6 1 1 6 7 1 1 7 5 1 1 5 4 1 1 Mie nu imi merge... :| Cu ce algoritm pot sa gasesc un drum mai lung dar cu watti mai putini astfel incat sa pot ajunge la destinatie, cum e in exemplul ? :-k Titlul: 102 Lanterna Scris de: u-92 din Februarie 10, 2006, 11:35:23 nu prea cred ca merge cu dijkstra.. ar trebui sa folosesti bellman ford cu coada, adica sa ai o matrice
Cod: T[i][j] = cost minim pt a ajunge in punctul i cu j wati pt mai multe detalii, problema a fost data la oji2004 Titlul: Raspuns: 102 Lanterna Scris de: Paul-Dan Baltescu din Aprilie 10, 2006, 22:48:04 Eu pic testele 6 si 9... ](*,) Am inteles ca e ceva mai "magic" la testul 9...Careva care a avut problema cu testul asta si s-a prins care era problema, poate sa dea un test asemanator aici? :'(
I could use any ideas privind si testul 6, bineinteles :) Titlul: Re: 102 Lanterna Scris de: Bogdan-Cristian Tataroiu din Aprilie 11, 2006, 08:06:47 Vezi daca pe teste la care toate drumurile au nevoie de energie 0 tu afisezi 1 sau 0... Daca citesti enuntul o sa vezi ca trebuie 1 <= W <= K
Titlul: Raspuns: 102 Lanterna Scris de: Paul-Dan Baltescu din Aprilie 11, 2006, 19:35:56 Nope...afisez 1 :sad:...
Titlul: Răspuns: 102 Lanterna Scris de: Barsan Paul din Martie 05, 2007, 19:06:41 Imi puteti explica va rog principiul de functionare al algoritmului "bellman ford cu coada". Nu m-am prins ce anume trebuie memorat in coada. Eu am incercat ceva de genu: iau primul nod, il adaug in coada parcurg toate muchiile care se leaga de acel nod si introduc in coada nodurile la care se micsoreaza valoare costului de la sursa la nodul i sau numarul de watti consumati. :?
Titlul: Răspuns: 102 Lanterna Scris de: Airinei Adrian din Martie 05, 2007, 19:38:18 Ideea ta este buna, cam asa functioneaza. Dar atentie la ce iti cere problema, intai te intereseaza W minim si apoi lungimea drumului sa fie minima. (hint: fixeaza intai W si apoi faci bellman-ford, o stare va fi caracterizata de nodul in care te afli si energia care a ajuns in el)
Titlul: Răspuns: 102 Lanterna Scris de: Ionescu Vlad din Iulie 15, 2007, 18:50:04 Imi dati va rog o idee pentru testul 9?
Am facut bellman ford cu coada. Cand scot un nod p din coada, adaug orice nod q legat de p doar daca en[p->nod] ( energia ajunsa in p pana in acel moment ) + q->en ( energia necesara parcurgerii ) <= w ( energia maxima pentru care caut distanta minima ).. Titlul: Răspuns: 102 Lanterna Scris de: Andrei Homorodean din Iulie 15, 2007, 19:39:07 Nici mie nu-mi mergea testul 9, eu cautam binar lanterna si faceam un fel de bf... faceam cautarea binara intre 1 si k-1... cand am pus limita dreapta k, am luat 100, deci daca te ajuta sunt destul de sigur ca pe testul 9 e kmin, k.
Titlul: Răspuns: 102 Lanterna Scris de: Ionescu Vlad din Iulie 15, 2007, 20:32:38 Eu inca nici nu am implementat cautarea binara, caut liniar lanterna, si totusi WA pe testul 9.
Daca afisez k si distanta returnata de Bellman Ford cu k iau 0 deci nu cred ca-i de la asta. :( Mi-ai putea spune cum ai verificat daca poti ajunge din nodul 1 in nodul n cu o anumita lanterna? Titlul: Răspuns: 102 Lanterna Scris de: Airinei Adrian din Iulie 15, 2007, 20:36:33 Uita-te si pe prima pagina de post-uri
Titlul: Răspuns: 102 Lanterna Scris de: Andrei Homorodean din Iulie 15, 2007, 20:56:56 Eu am o matrice min, min[ x ][ y ] = timpul minim pana la nodul x, cu y energie consumata, mai tin si o coada... By the way.. vezi ca tre sa gasesti la inceput timpul minim pentru k. Abia apoi cauti o lanterna(de capacitate mai mica) pentru care se obtine acelasi timp.
Titlul: Răspuns: 102 Lanterna Scris de: Ionescu Vlad din Iulie 15, 2007, 21:30:43 Eu nu am facut cu matrice... eu tin doi vectori d si en, d[ i] = distanta minima pana in nodul i ( daca nu se poate ajunge cu o lanterna de valoare w, atunci este infinit ) si en[ i] = energia ajunsa pana in nodul i. Cand vreau sa expandez un nod din coada, ma folosesc de vectorii astia...
O sa incerc s-o fac si cu matrice, vad ca nu vrea nicicum cum m-am gandit eu... Titlul: Răspuns: 102 Lanterna Scris de: Andrei Homorodean din Iulie 15, 2007, 21:43:41 Ciudat ca ti-a mers de 90 sau tu bagi elemente in coada chiar daca nu sunt optime in momentul acela. Poti sa ai un drum cu un timp 10 pana in nodul x si energie insuficienta ca sa mai poti inainta, si sa mai ai inca unul cu un timp 20 si energie suficienta sa continui drumul. Prima configuratie ti-o cam blocheaza pe a2-a..
Titlul: Răspuns: 102 Lanterna Scris de: Ionescu Vlad din Iulie 15, 2007, 22:35:31 Pai fac bellman ford..
Adica bag un nod in coada de fiecare data cand ii pot imbunatati costul, daca nu se afla deja in coada, si daca pot ajunge la el cu energia ramasa. Astfel, fiecare nod poate sa fie in coada de maxim n ori. Chiar daca se blocheaza a doua varianta, pentru un w mai mare tot voi avea posibilitatea sa merg pe primul drum... desi asta numai daca costul energetic al unei deplasari nu este mai mare decat k :-k Daca este... da, cred ca as pica pe un asemenea test... Titlul: Răspuns: 102 Lanterna Scris de: Bula Ionut din Februarie 21, 2008, 16:51:37 tare as vrea sa vad si eu cum arata un Bellman Ford cu coada. stiu cum arata algoritmul fara coada, nu cumva are O(n^3) ? se poate totusi sa nu stiu eu.
Titlul: Răspuns: 102 Lanterna Scris de: Adrian Diaconu din Februarie 23, 2008, 12:34:23 Cod: Q.push(sursa) Functia relaxeaza compara minimul obtinut pana atunci pentru y cu minimul pentru x + costul pentru muchia (x,y). In cazul in care acest cost este mai mic y se introduce in coada. Ca o optimizare se poate tine un vector auxiliar in care se marcheaza daca un nod este sau nu in coada si se introduce doar in cazul in care acesta nu se afla deja.while !Q.empty { x=Q.top() Q.pop() for y vecin cu x relaxeaza(x,y) } Chiar daca complexitatea teoretica este O(n*m) in practica se comporta destul de bine algoritmul. Titlul: Răspuns: 102 Lanterna Scris de: Bula Ionut din Februarie 23, 2008, 13:42:07 Mersi...
Titlul: Răspuns: 102 Lanterna Scris de: Philip din Martie 09, 2009, 15:31:55 Trebuie determinat intai drumul minim (durata minima), si tipul de lanterna necesara pentru acest drum, sau tipul de lanterna trebuie sa fie minim, si in functie de el, durata minima a drumului?
Din textul problemei se intelege prima varianta. Titlul: Răspuns: 102 Lanterna Scris de: Florian Marcu din Martie 09, 2009, 17:20:20 Trebuie determinat exact ceea ce se intelege din enunt. Adica drumul minim, si tipul de lanterna cu care se poate parcurge acest drum minim. :)
Titlul: Răspuns: 102 Lanterna Scris de: Philip din Martie 09, 2009, 19:13:05 Se poate sa existe drumuri minime pentru care nici un tip de lanterna nu este posibil, atunci programul meu fiind nevoit sa gaseasca un drum mai lung?
Era mai sus un astfel de exemplu... Cod: 8 6 Daca sunt astfel de cazuri, nu pot sa caut tipul de lanterna potrivit doar dupa ce am gasit drumul minim. Trebuie sa tin cont de asta cand caut drumul.0 0 0 0 0 0 0 0 8 1 2 1 2 2 3 1 2 3 4 1 2 4 8 1 1 1 6 1 1 6 7 1 1 7 5 1 1 5 4 1 1 Imi da numai 40 de pct pe problema... 4 rezultate incorecte (inca incerc sa vad ce am gresit) si 2 afara din timp (cred ca din cauza ca folosesc bellman-ford fara coada). Titlul: Răspuns: 102 Lanterna Scris de: Florian Marcu din Martie 09, 2009, 19:28:17 Se poate sa existe drumuri minime pentru care nici un tip de lanterna nu este posibil, atunci programul meu fiind nevoit sa gaseasca un drum mai lung? Da. Titlul: Răspuns: 102 Lanterna Scris de: Antoche Ioana Alexandra din Februarie 01, 2010, 20:31:53 Cat trebuie sa dea pe ex:
Cod: 8 6 ?1 1 1 1 1 1 1 1 8 1 2 1 0 2 3 1 0 3 4 1 0 4 8 1 0 1 6 1 0 6 7 1 0 7 5 1 0 5 4 1 0 4 1 sau 4 0? Titlul: Răspuns: 102 Lanterna Scris de: Tirca Bogdan din Februarie 02, 2010, 09:34:28 Nu am verificat dar daca ai calculat tu bine timpu trebuie sa afisezi 4 1, nu exista tip de lanterna 0
Titlul: Răspuns: 102 Lanterna Scris de: Tuchila Octavian din Aprilie 15, 2010, 11:41:01 nu prea cred ca merge cu dijkstra.. ar trebui sa folosesti bellman ford cu coada, adica sa ai o matrice Cum se poate forma matricea Cod: T[i][j] = cost minim pt a ajunge in punctul i cu j wati pt mai multe detalii, problema a fost data la oji2004 Cod: T[i][j] folosind Bellman-Ford ?Titlul: Răspuns: 102 Lanterna Scris de: Andrei Pleshka din Mai 10, 2010, 20:32:30 Editat de moderator
Nu se injura pe aici! Titlul: Răspuns: 102 Lanterna Scris de: Vlad Eugen Dornescu din Martie 04, 2011, 23:43:53 Cand se foloseste cautarea binara la problema asta? :)
Titlul: Răspuns: 102 Lanterna Scris de: Lepadat Mihai-Alexandru din Martie 05, 2011, 09:37:29 Cand cauti tipul de lanterna.
Titlul: Răspuns: 102 Lanterna Scris de: Vlad Eugen Dornescu din Martie 05, 2011, 10:02:58 Citat din enunt : iar daca ar alege o lanterna de un tip mai mare decat W, durata deplasarii ar fi mai mare sau egala.
N-ar trebui sa fie doar 'egala' acolo ? Daca pentru un K solutie obtin timpul minim T, inseamna ca pentru orice alt k > K obtin timpul minim T. Graful e tot timpul acelasi, inseamna ca pentru k mai mare decat K voi obtine acelasi timp minim T.Iar daca K nu e rezultatul cautat, atunci pt orice K > k obtin un T mai mic? Titlul: Răspuns: 102 Lanterna Scris de: Sorin Rita din Ianuarie 10, 2012, 22:48:16 Imi puteti da o idee despre cum sa trec testul 9 ? Chiar e provocator. Nu imi pot da seama in ce situatie nu ar merge algoritmul meu. Zicea cineva mai sus ca e sigur ca testul asta are kmin=k dar nu mi se trage de la asta.
Titlul: Răspuns: 102 Lanterna Scris de: Boaca Cosmin din Februarie 27, 2012, 18:41:51 Testul 7 e ala provocator ? ca nu il trec sub niciun chip .
Titlul: Răspuns: 102 Lanterna Scris de: theo .c din Februarie 25, 2013, 01:39:08 Cat da pentru? ](*,)
Cod: 50 999 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 229 1 3 36 423 1 5 72 11 1 20 75 27 1 24 10 419 1 30 41 329 1 31 38 377 1 33 27 383 1 37 33 391 1 45 35 417 2 4 53 410 2 9 33 327 2 11 52 385 2 16 73 15 2 17 38 365 2 25 30 415 2 27 83 6 2 32 7 376 2 44 47 364 3 5 91 40 3 20 94 22 3 24 65 355 3 30 51 412 3 31 61 446 3 33 18 300 3 37 26 396 3 45 29 307 4 9 10 311 4 11 99 37 4 13 99 180 4 16 14 392 4 17 63 322 4 25 98 40 4 27 40 316 4 32 21 377 4 44 89 15 5 14 99 394 5 20 27 368 5 24 1 306 5 30 69 341 5 31 21 323 5 33 89 24 5 37 54 419 5 45 88 15 6 10 9 347 6 22 3 412 6 23 36 341 6 34 79 5 6 36 88 9 6 42 95 46 6 47 72 32 6 48 22 423 6 49 44 417 7 8 68 285 7 13 32 293 7 14 54 276 7 15 34 402 7 21 98 12 7 35 45 367 7 38 16 323 7 39 76 30 7 43 18 274 8 13 61 396 8 14 61 294 8 15 49 346 8 21 6 315 8 35 73 35 8 38 100 1 8 39 65 447 8 43 54 306 9 11 64 266 9 16 40 430 9 17 95 36 9 25 14 339 9 27 56 333 9 32 30 335 9 44 74 37 10 22 60 440 10 23 57 373 10 34 96 44 10 36 87 47 10 42 70 7 10 47 99 13 10 48 57 361 10 49 35 309 11 16 19 343 11 17 85 29 11 25 68 250 11 27 36 402 11 32 92 8 11 44 99 9 12 18 16 340 12 19 78 30 12 26 14 421 12 28 60 342 12 29 90 44 12 40 71 11 12 41 54 349 12 46 65 379 12 50 95 18 13 14 39 358 13 15 93 38 13 21 66 332 13 35 9 259 13 38 55 285 13 39 83 36 13 43 10 315 14 15 92 36 14 21 91 42 14 35 50 294 14 38 18 333 14 39 3 295 14 43 65 398 15 21 25 321 15 35 39 288 15 38 18 376 15 39 82 5 15 43 85 5 16 17 55 327 16 25 16 314 16 27 53 343 16 32 70 23 16 44 15 386 17 25 51 434 17 27 31 252 17 32 92 48 17 44 73 38 18 19 25 312 18 26 79 20 18 28 44 409 18 29 67 430 18 40 30 443 18 41 68 306 18 46 43 383 18 50 38 445 19 26 38 420 19 28 68 328 19 29 46 378 19 40 96 41 19 41 11 293 19 46 1 402 19 50 97 42 20 24 68 251 20 30 66 281 20 31 92 0 20 33 1 401 20 37 96 4 20 45 49 431 21 35 65 434 21 38 65 378 21 39 3 276 21 43 73 24 22 23 96 46 22 34 44 273 22 36 46 385 22 42 71 7 22 47 8 382 22 48 1 423 22 49 73 23 23 34 40 396 23 36 35 375 23 42 81 18 23 47 36 256 23 48 88 16 23 49 64 295 24 30 8 395 24 31 94 38 24 33 42 282 24 37 6 319 24 45 7 358 25 27 87 28 25 32 53 426 25 44 66 252 25 49 99 365 26 28 68 364 26 29 37 281 26 40 5 317 26 41 78 38 26 46 54 346 26 50 24 263 27 32 62 360 27 44 24 427 28 29 33 375 28 40 46 279 28 41 78 2 28 46 45 367 28 50 20 422 29 40 59 309 29 41 8 316 29 46 99 3 29 50 2 305 30 31 81 21 30 33 48 333 30 37 38 337 30 45 76 12 31 33 84 7 31 37 96 20 31 45 77 10 32 44 62 257 33 37 13 411 33 45 35 415 34 36 89 42 34 42 30 347 34 47 2 427 34 48 71 13 34 49 17 380 35 38 87 40 35 39 14 360 35 43 28 285 36 42 27 301 36 47 73 24 36 48 33 380 36 49 21 339 37 45 27 380 38 39 57 281 38 43 68 358 39 43 6 367 40 41 38 436 40 46 22 405 40 47 99 210 40 50 45 381 41 46 54 353 41 50 32 418 42 47 100 6 42 48 85 41 42 49 57 268 46 50 73 24 47 48 41 432 47 49 38 357 48 49 83 41 Am scris 2 implementari pe cat de diferite am putut si iau numai incorect. Titlul: Răspuns: 102 Lanterna Scris de: Radu-Andrei Szasz din Februarie 25, 2013, 11:24:27 Cod: 672 580 Titlul: Răspuns: 102 Lanterna Scris de: theo .c din Februarie 26, 2013, 23:05:54 Thanks. :ok: Eu calculam drumul minim fara sa tin cont de K.
Titlul: Răspuns: 102 Lanterna Scris de: Alghisi Alessandro Paolo din Martie 01, 2013, 14:03:10 Aceeasi sursa aici ia 90p iar pe .campion 100 :) Ce are special aici testul 9 ? ???
Titlul: Răspuns: 102 Lanterna Scris de: Pirtoaca George Sebastian din Martie 01, 2013, 14:24:32 Am schimbat un test cu unul mai "provocator" si am reevaluat problema. (In caz ca va intrebati de ce unii au cu 10p mai putin decat inainte). :pimp: Cred ca asta e motivul. :DTitlul: Răspuns: 102 Lanterna Scris de: Alghisi Alessandro Paolo din Martie 01, 2013, 15:12:50 Mda , un test atat de provocator incat majoritatea au 0/4 ms pe el :D Si scuze , nu citisem acea postare :)
Titlul: Răspuns: 102 Lanterna Scris de: Pirtoaca George Sebastian din Martie 01, 2013, 15:18:22 Intotdeauna testele mici sunt cele provocatoare.
Titlul: Răspuns: 102 Lanterna Scris de: Gemene Narcis - Gabriel din Aprilie 17, 2013, 19:42:36 Imi arati si mie testul 9? :D
Titlul: Răspuns: 102 Lanterna Scris de: hiticasabel din Iunie 18, 2013, 12:35:42 Personal cred ca ar trebui marit putin timpul de executie pe test. Sursa oficiala ia doar 90 de puncte cu TLE pe testul 7...
Titlul: Răspuns: 102 Lanterna Scris de: Vasile Catana din Ianuarie 05, 2015, 13:22:31 solved
Titlul: Răspuns: 102 Lanterna Scris de: Stoian Mihail din Iulie 09, 2015, 15:27:03 Stiu ca suna cam dubios, dar merge cu un singur Bellman-Ford?(doar intreb ca poate, poate, cineva s-a mai gandit la ideea asta). :oops:
Eu m-am gandit ca se poate pleca cu parcurgerea din nodul N, calculand pentru fiecare nod necesarul minim de watti pe care trebuie sa-i folosim pentru a obtine distanta minima. Am implementat ceva care ia doar 10 puncte, dar sunt sigur ca aceasta idee trebuie sa mearga. :thumbup: Daca vede cineva comentariul acesta, il rog sa se gandeasca la ideea aceasta ca poate va reusi sa o implementeze perfect (eu ma voi stradui in continuare :D). Titlul: Răspuns: 102 Lanterna Scris de: Stoian Mihail din Iulie 11, 2015, 13:21:55 Da, merge! :ok:
Am pornit Bellman-Ford-ul din nodul 1(nu din nodul N - cum am zis in comentariul trecut). Deci, cine vrea sa implementeze aceasta idee, chiar ii recomand (e foarte asemanatoare cu cea de complexitate O(K * M * N)). Cine vrea sa vada timpii - * ID: http://www.infoarena.ro/job_detail/1459472 (complexitate O(K * M * N)) * ID: http://www.infoarena.ro/job_detail/1460000 (complexitate O(M * N)) Bafta! :D Titlul: Răspuns: 102 Lanterna Scris de: Dumitru Corneliu din Noiembrie 26, 2015, 18:59:31 Poate sa-mi dea cineva testul 9?
Titlul: Răspuns: 102 Lanterna Scris de: Axinie Razvan din Decembrie 13, 2015, 14:09:31 Ce pana corbului are asa special testul 9?
|