977 Semafoare

[•pauldb]

Aici puteti discuta despre problema Semafoare.

[•Mishu91]

Am o întrebare în legătură cu al doilea exemplu. Cum dă 19? Mie îmi dă 15 pe următorul traseu(am pus nodurile și timpu cât durează de când începe până traversează intersecția cu pricina):
0 5 -> 2
1 5 -> 4
1 4 -> 6
1 3 -> 9
2 3 -> 10
2 2 -> 12
3 2 -> 14
Deci în 3 1 va ajunge în momentul 15. 

[•pauldb]

Odată intrată în intersecţie o maşină îşi poate continua drumul mai departe sau poate vira spre stânga sau spre dreapta.

Tu in intersectia (0, 5) te intorci, ceea ce nu e permis.

[•Mishu91]

N-am citit restricția respectivă considerând că oricum nu are de ce să se întoarcă (iar în afară de cazul în care se întoarce în prima intersecție, nu are de ce să se întoarcă).

Ca o optimizare a soluției oficiale, nu are sens să reținem maximul pentru un triplet (i, j, k), ci doar pentru perechea (i, j), întrucât direcția din care se vine nu are relevanță decât pentru a calcula cât timp stă la semafor. De aceea, când trece dintr-o stare în alta, se poate calcula timpul noii stări ca fiind timpul vechii stări + timpul cât stă la semafor în noua stare + 1. Deși complexitatea teoretică este tot O(N*M), în realitate merge mult mai repede (sub 0,2 secunde).

P.S. Linku către problemă din primul post este greșit (scrie infoarnea în loc de infoarena).

[•Mitza444]

Buna!Imi puteti explica un pic mai detaliat rezolvarea problemei.Am citit solutia oficiala,dar nu am inteles prea bine cum se face acea parcurgere folosind cele 5 cozi si matricea D cu cele 3 dimensiuni  .
Multumesc.

[•pauldb]

Ai putea incerca sa rezolvi problema http://infoarena.ro/problema/padure mai intai. Aceasta problema este asemanatoare, dar mai simpla si sunt ceva explicatii si pe forum despre cum se rezolva in caz ca nu te descurci.