1092 Joculet

[•wefgef]

Aici puteti discuta despre problema Joculet.

[•Bit_Master]

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

[•SpiderMan]

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.

[•Bit_Master]

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)

[•SpiderMan]

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 .

[•APOCALYPTO]

D[ i ][ i ] = V[i ] pentru 1 ≤ i ≤ N
D[ i ][j] = max(V[ i ] - D[i + 1][j], V[j] - D[ i ][j - 1]), i ≠ j
D[ i ][j] = max(D[ i][j], V[ i ] + V[j] - D[i + 1][j - 1]), j - i ≥ 2
Solutia se va afla in D[1][N].
Pentru a obtine insa 100 de puncte nu trebuie retinuta intreaga matrice, ci doar ultimele doua linii.

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

[•pauldb]

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.

[•Pepelea_Flaviu]

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 .

[•Bit_Master]

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 ]).

[•APOCALYPTO]

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 .

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[][].

[•wefgef]

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

[•login]

Care este raspunsul corect pentru :
3
8 12 -5

[•SpiderMan]

Cod:

-9

[•login]

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).

[•pauldb]

Sa se determine diferenta maxima dintre punctajul primului si celui de-al doilea jucator, diferenta care poate fi obtinuata in cel mai rau caz, indiferent de cum joaca cel de-al doilea jucator.

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

[•SpiderMan]

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 .