053 Car

[•domino]

Aici puteţi discuta despre problema Car.

[•masterthor]

indexarea pozitiilor initiale si finale incepe de la 0 sau la 1 ? adika primul element din matrice e A[0,0] sau A[1,1] ?

[•rss1987]

Nasol testu 9.  L-a facut cineva din prima? Tot iau TLE.
 Da cu bellman-ford a facut careva?, eu asa am facut si merge binisor, poate chiar mai bine decat Dijkstra cu costuri mici. M-am uitat la solutia prezentata oficial, pare simplu, dar tocmai constanta din fata lu' N*M care este 3*8*(cate operatii efectuate cu un nod din lista) si care nu este precizata face diferenta de scor. In cazurile astea constanta n-ar trebui ignorata, e importanta!!!

[•Cosmin]

Testul 9 este cel mai costisitpr ca timp si pentru solutia noastra care sta pe el in jur de 0.5 secunde.

[cip2005]

Eu totusi nu inteleg o chestie in rezolvare, legata de listele folosite..  :

Daca aceste costuri sunt mici atunci si costul final al drumului de la sursa la destinatie va fi mic deci ne permitem sa folosim pentru fiecare valoare posibila a costului unui drum de la sursa la destinatie cate o lista.

si totusi ce aflam noi mai tarziu?! ca sunt 3 liste defapt! :

Am folosit numai trei liste pentru ca am tinut cont de optimizarea precizata mai sus de a nu folosi numai curbele la 0 grade, 45 grade si 90
grade.

va rog sa ma ajutati si pe mine sa ma lamuresc... [/quote]

[•Cosmin]

Pai ai daca la pasul actual expandezi noduri la care s-a ajuns cu costul C, atunci vei modifica numai listele cu costul C, C+1 si C+2, deci listele nu  cu cost C-1 C-2 .... 0 nu mai are rost sa le folosesti, iar listele de cost C+3, C+4 .... sunt inca nepopulate, deci poti folosi numai 3 liste si faci ceva de genu:

Cod:

  while (l[0].size > 0 && l[1].size() > 0 && l[2].size() > 0) {
      while (l[C % 3].size() > 0) {
            X = l[C % 3].pop();
            expand(X);
      }
      C++;      
  }

 Tot asa faci la unele programari dinamice in care in loc sa folosesti o matrice intreaga folosesti doar doua linii, linia curenta si linia urmatoare.

[•pauldb]

Puteti sa-mi spuneti cat va da pe testul:

15 15
8 8 10 14
1 0 0 0 0 1 0 0 1 1 1 0 1 1 0
0 0 1 1 1 1 0 0 0 1 0 0 0 1 1
0 1 1 0 1 0 0 1 0 0 0 0 1 0 1
0 1 1 1 0 0 1 1 1 1 0 0 1 1 1
0 0 1 1 0 0 0 0 1 0 0 0 0 1 1
0 0 0 0 1 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 1 1 0 1
1 0 0 1 0 1 1 0 0 0 1 0 1 0 1
1 1 0 0 0 0 1 0 1 0 0 0 0 1 0
1 0 0 1 0 1 0 0 0 1 1 1 1 0 1
0 0 0 1 0 0 0 1 0 0 0 0 0 0 1
1 0 1 0 1 0 1 1 0 1 0 1 1 1 1
1 1 1 0 0 0 1 1 1 0 1 0 0 1 0
0 1 0 1 0 0 1 1 0 0 0 0 0 0 1
0 0 1 1 1 1 1 0 0 1 0 0 0 0 0

[•bogdan2412]

2  

[•Marius]

Ma chinui de o zi sa trec testele 7 si 10, e ceva special la ele ? Pot sa le rezolv luand numai curbe de 0 , 45 si 90 de grade, nu ? 

[•Cosmin]

Poti sa o rezolvi doar cu curbe de 0 si 45, fara 90, daca vei considera ca miscarea pe loc cu 45 de grade costa 1.

[•Marius]

Nu sunt sigur daca am rezolvat corect, pentru ca nu trect testele 7 si 10, dar  9 dureaza 0.22 s.
Am incercat sa rezolv problema cam asa: iau numai curbe de 0, 45, 90 de grade. Cand verific vecinii nodului curent si gasesc un cost mai mic sau egal il pun in coada. Coada asta are trei "niveluri", adica daca nodul curent se afla pe nivelul k , atunci cand inserez un nod vecin il pe nivelul (k + dir) % 3, unde dir e 0 daca se continua pe directia respectiva, e 1 daca e o curba de 45 si 2 daca e curba de 90 de grade. Continui pana cand "golesc" nivelul curent, apoi trec la urmatorul. Totul se termina cand toate nivelurile sunt goale.

Putin ajutor! 

[•filipb]

Ai verificat sa nu adaugi de doua ori un nod in liste? Adica cand ai adaugat un nod intr-o lista pentru prima data, il marchezi ca FOLOSIT si nu il mai adaugi in vreuna din liste si a doua oara.

[•Marius]

Nu gasesc un exemplu, dar daca nu pun un nod de mai multe ori (de cel mult trei ori, deoarece poti intra in el din cel mult trei directii) pot sa continui de aici cu un cost mai mare, depinzand de directie. Cum zici tu iau 50 p. 

[•Cosmin]

Pentru fiecare nod tii minte distanta minima cu care ai ajuns la el, si cand vrei sa il adaugi la o lista, il adaugi doar daca indicele real al listei este mai mic decat distanta calculata pana in momentul curent.

[•raula_san]

Pentru exemplul din enunt, raspunsul nu ar trebui sa fie 11 ? Ionel ia 3 curbe de 90 de grade si una de 135 ...

[•lsorin_94]

@chris nup, ia doar curbe de 45; iar ultima de pe ultima coloana este de 135

[•PlayLikeNeverB4]

Nu sunt curbe de 135 in exemplu. Ai 4 de 90 si una de 45.