102 Lanterna

[•Dastas]

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

[•peanutz]

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.

[•Dastas]

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?

[•astronomy]

Uita-te si pe prima pagina de post-uri

[•peanutz]

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.

[•Dastas]

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

[•peanutz]

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

[•Dastas]

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

Daca este... da, cred ca as pica pe un asemenea test...

[•cosser]

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.

[•DITzoneC]

Cod:

Q.push(sursa)
while !Q.empty
{
    x=Q.top()
    Q.pop()
    for y vecin cu x
        relaxeaza(x,y)    
}

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.

Chiar daca complexitatea teoretica este O(n*m) in practica se comporta destul de bine algoritmul.

[•cosser]

Mersi...

[•philip]

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.

[•Florian]

Trebuie determinat exact ceea ce se intelege din enunt. Adica drumul minim, si tipul de lanterna cu care se poate parcurge acest drum minim. 

[•philip]

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

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.

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

[•Florian]

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.

[•Alexa_ioana_14]

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?

[•Bogdan_tmm]

Nu am verificat dar daca ai calculat tu bine timpu trebuie sa afisezi 4 1, nu exista tip de lanterna 0

[•ooctav]

 

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

Cum se poate forma matricea

Cod:

T[i][j] 

folosind Bellman-Ford ?

[•ANDRY1990]

Editat de moderator
Nu se injura pe aici!

[•dornescuvlad]

Cand se foloseste cautarea binara la problema asta?

[•skull]

Cand cauti tipul de lanterna.

[•dornescuvlad]

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?

[•soriyn]

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.

[•darkseeker]

Testul 7 e ala provocator ? ca nu il trec sub niciun chip .

[•Theory]

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.