|
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 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:
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:
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) 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 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 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] 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 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 meitatiidirect.ro 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 meitatiidirect.ro 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?
|