infoarena

Aici puteti discuta despre problema Joculet (http://infoarena.ro/problema/joculet).

De ce e limita de timp pusa asa de strans de N^2 depaseste la limita?

Nu e stransa, din cate vad sursa ta, si a multor care iau 60 puncte, nu e dinamica corecta, e gresita. Din acea cauza ai un incorect, si din intamplare ai luat celelalte teste. Fa dinamica corecta, si ai sa vezi ca iei 100 puncte lejer.

nu prea cred ca e gresita, ca e verificata, dar in fine (dinamica nu e gresita, o fi vre-un test particular care nu-mi vine in minte)

Iti spun eu sigur, spre exemplu iti poate spune Oprica Dragos, care are aceleasi rezultate ca si tine ( 60 puncte, acelasi Incorect si 2 TLE ) , ca are o dinamica gresita. Daca vrei poti pune aici cum ai facut-o, si o sa-ti spuna daca e gresita sau nu ;) .

Care sunt ultimele 2 linii?
Nu cumva trebuia diagonale? Si chiar si asa cum as putea tine ultimele 2 diagonale?

Eu am transformat dinamica respectiva in D[ i ][ j ] = suma maxima pe care o poate obtine primul jucator pe o secventa de lungime i care incepe la pozitie j. Am avut nevoie de ultimele 3 linii, dar merge. :)

Ajunge sa retii doar ultimele 2 linii. Dupa cum se observa si din recurenta din articolul de solutii, la fiecare pas nu ai nevoie decat de linia i si i + 1. Iar in legatura cu memoria, vroiam sa pun limita 648kb, dar nu prea am eu permisiunea asta, pentru ca problema nu a fost adaugata de pe contul meu. Poate se ofera vreun admin sa modifice limita :).

Eu m-am gandit asa:

a[ i ][ j ] -> diferenta maxima care o poate obtine jucatorul care este la mutare daca are la
          dispozitie o tabla cu nr de la i la j

a[ i ][ j ] = max(v[ i ] - a[ i+1 ][ j ], v[ j ] - a[ i ][ j-1 ], v[ i ] + v[ j ] - a[ i+1 ][ j-1 ]);

si parcurg matricea luand intai elem de lungime 1 (a[ i ][ i ]), de lungime 2 (a[ i ][ i+1 ])...pana la cea finala de lungime n (a[ 1 ][ n ]).

Oups  :?!  Asa este, nu stiu de ce am avut impresia ca nu se poate cu 2 linii, cred ca m-au derutat j-urile.
Acum iau 70 pe sursa facuta cu 2 linii cu relatia din articolul de solutii.
Si vad ca mai sunt si altii care au picat testele 4,9,10.
Ce contin special aceste teste?

Later edit: Am luat 100, problema era de la faptul ca declaram numerele de pe tabele int, in loc de long long, sau nu faceam conversia cand calculam matricea dp[][].

Am modificat limita de memorie si am reevaluat sursele din arhiva.

Care este raspunsul corect pentru :
3
8 12 -5

-9

Pentru
3
8 12 -5
nu se poate si in felul urmator? primul jucator alege 8, al doilea -5, apoi primul 12, cu diferenta 25 (25> -9).

Nu e bine cum spui tu, deoarece al doilea jucator joaca optim (cauta sa minimeze diferenta).

Corect e ca primul sa ia pe 8 si pe -5 ( sa nu-l lase pe al doilea sa ia pe -5, sa minimeze diferenta ) , si al doilea il ia pe 12, care a mai ramas. Rezultatul este ( 8-5 ) - 12 = -9 .