102 Lanterna

[•domino]

Aici puteţi discuta despre problema Lanterna.

[•cristy]

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

[•bogdan2412]

5 3

[•cristy]

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

[•calinux]

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?    Mersi!

[•bogdan2412]

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.

[•cristy]

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?

[•bogdan2412]

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

[•domino]

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

[•calinux]

   
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...  
Raman etern recunoscator pentru orice hint.  

[cristi8]

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

[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

[•calinux]

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?

[cristi8]

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.

[•greco]

Atentie ca o mic nu e tot una cu O mare.

[•calinux]

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   care este diferenta intre o si O ? Mersi mult!

[•DeadStar]

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.

[•calinux]

Mersi... Util de stiut!   Dar totusi in legatura cu algoritmul meu... are cineva vreo/vreun sugestie/critica/sfat?

[•wefgef]

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

[•Marius]

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 ?  

[u-92]

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

[•pauldb]

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

[•bogdan2412]

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

[•pauldb]

Nope...afisez 1 ...

[•megabyte]

      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.

[•astronomy]

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)