982 Joc13

[•stef2n]

Aici puteti discuta despre problema Joc13.

[•DEYDEY2]

hmmmm
programare dinamica?

[•PlayLikeNeverB4]

Da. Iese frumos cu memoizare. Este o astfel de solutie printre solutiile oficiale.

[•flaviusc11]

Eu am facut recursiv, dar iau doar 20 de puncte.

[•PlayLikeNeverB4]

Trebuie sa retii starile deja calculate intr-o matrice. Starile sunt caracterizate de i,j,k,d, unde i-linia, j-coloana, k-nr de coloane consecutive, d-directia din care am intrat in celula. Cand apelezi recursiv drum(i,j,k,d) de exemplu si ai calculat deja inainte asta atunci nu mai trebuie sa o faci inca odata.

[•CalinRadu91]

ce sens mai are variabila d cand e clar ca pt k=1 se vine de pe cealalta linie, altfel se vine din stanga(exceptand cazul primei coloane)?

[•PlayLikeNeverB4]

Exista caz cand poti trece la cealalta linie "prematur", inainte sa ajungi la limita lui k.

[•CalinRadu91]

pai da..asta se poate intampla pt orice k>1.. gresesc cumva?

[•PlayLikeNeverB4]

Aaa, da. Acum am realizat la ce te refereai. Probabil ca merge si asa, nu m-am gandit la asta. M-am inspirat din solutia oficiala

[•dutzul]

hm eu am facut exact asa ca si  cum zice PlayLikeNeverB4George Marcus •PlayLikeNeverB4 doar ca nerecursiv;(un bellman ford)
iau doar 60 de pcte cu tle ar trebui sa intri adica am 2*2*N*L=5000*40 worst case

[•repp4radu]

Eu am facut iterativ si am intrat lejer in timp(8 ms) cu O(N * K). Incearca sa mai optimizezi ca intra 

[•vld7]

am o dinamica D[ i ][ j ][ k ] = valoarea maxima pana in (i, j) venind din stanga pe ultimele k coloane si V[ i ][ j ] = valorea maxima pana (i, j), ultima mutare fiind schimbarea liniei.

Iau 2 wa si nu ma prind de ce, solutia oficiala tot cam asa face. Un hint sau un test mai mic pe care sa-mi pice ?

[•Eberardo]

Iau sigfpe la toate testele desi nu am impartiri in cod..idei?

[•Eberardo]

Rectificare, am un %, dar n-are cum sa ajunga sa imparta la 0..