|
Titlul: 982 Joc13 Scris de: Stefan Istrate din Martie 07, 2010, 20:56:02 Aici puteti discuta despre problema Joc13 (http://infoarena.ro/problema/joc13).
Titlul: Răspuns: 982 Joc13 Scris de: Tudorica Andrei din Februarie 12, 2011, 20:36:40 hmmmm
programare dinamica? :-' Titlul: Răspuns: 982 Joc13 Scris de: George Marcus din Februarie 13, 2011, 00:37:42 Da. Iese frumos cu memoizare. Este o astfel de solutie printre solutiile oficiale.
Titlul: Răspuns: 982 Joc13 Scris de: Fl. C. din Martie 17, 2011, 21:52:36 Eu am facut recursiv, dar iau doar 20 de puncte.
Titlul: Răspuns: 982 Joc13 Scris de: George Marcus din Martie 17, 2011, 23:58:02 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.
Titlul: Răspuns: 982 Joc13 Scris de: Calin Radu Calin din Martie 18, 2011, 17:07:45 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)?
Titlul: Răspuns: 982 Joc13 Scris de: George Marcus din Martie 18, 2011, 18:30:18 Exista caz cand poti trece la cealalta linie "prematur", inainte sa ajungi la limita lui k.
Titlul: Răspuns: 982 Joc13 Scris de: Calin Radu Calin din Martie 18, 2011, 19:31:08 pai da..asta se poate intampla pt orice k>1.. gresesc cumva?
Titlul: Răspuns: 982 Joc13 Scris de: George Marcus din Martie 18, 2011, 19:56:22 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 :)
Titlul: Răspuns: 982 Joc13 Scris de: Bodnariuc Dan Alexandru din Noiembrie 19, 2012, 22:31:44 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 :-k Titlul: Răspuns: 982 Joc13 Scris de: Radu-Andrei Szasz din Noiembrie 19, 2012, 22:52:28 Eu am facut iterativ si am intrat lejer in timp(8 ms) cu O(N * K). Incearca sa mai optimizezi ca intra :)
Titlul: Răspuns: 982 Joc13 Scris de: Campeanu Vlad din Februarie 14, 2013, 21:11:34 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 ? Titlul: Răspuns: 982 Joc13 Scris de: Vladianu Cosmin din Ianuarie 16, 2016, 19:37:48 Iau sigfpe la toate testele desi nu am impartiri in cod..idei?
Titlul: Răspuns: 982 Joc13 Scris de: Vladianu Cosmin din Ianuarie 16, 2016, 20:24:21 Rectificare, am un %, dar n-are cum sa ajunga sa imparta la 0..
|