Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 1092 Joculet  (Citit de 2605 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« : Decembrie 13, 2010, 00:37:53 »

Aici puteti discuta despre problema Joculet.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Bit_Master
Vorbaret
****

Karma: -49
Deconectat Deconectat

Mesaje: 159



Vezi Profilul
« Răspunde #1 : Decembrie 14, 2010, 19:19:25 »

De ce e limita de timp pusa asa de strans de N^2 depaseste la limita?
Memorat
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #2 : Decembrie 14, 2010, 19:26:56 »

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.
Memorat
Bit_Master
Vorbaret
****

Karma: -49
Deconectat Deconectat

Mesaje: 159



Vezi Profilul
« Răspunde #3 : Decembrie 14, 2010, 20:07:04 »

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)
Memorat
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #4 : Decembrie 14, 2010, 21:02:55 »

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 Wink .
Memorat
APOCALYPTO
Nu mai tace
*****

Karma: 3
Deconectat Deconectat

Mesaje: 250



Vezi Profilul
« Răspunde #5 : Decembrie 15, 2010, 00:38:38 »

Citat
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?
Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #6 : Decembrie 15, 2010, 10:56:13 »

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. Smile
Memorat

Am zis Mr. Green
Pepelea_Flaviu
Client obisnuit
**

Karma: 30
Deconectat Deconectat

Mesaje: 98



Vezi Profilul
« Răspunde #7 : Decembrie 15, 2010, 14:59:37 »

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 Smile.
Memorat
Bit_Master
Vorbaret
****

Karma: -49
Deconectat Deconectat

Mesaje: 159



Vezi Profilul
« Răspunde #8 : Decembrie 15, 2010, 15:01:13 »

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 ]).
« Ultima modificare: Decembrie 15, 2010, 15:14:10 de către Gabriel Bitis » Memorat
APOCALYPTO
Nu mai tace
*****

Karma: 3
Deconectat Deconectat

Mesaje: 250



Vezi Profilul
« Răspunde #9 : Decembrie 15, 2010, 18:32:13 »

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 Smile.
Oups  Confused!  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[][].
« Ultima modificare: Decembrie 15, 2010, 19:20:53 de către Dragos » Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #10 : Decembrie 15, 2010, 19:07:02 »

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

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
login
Strain


Karma: 3
Deconectat Deconectat

Mesaje: 4



Vezi Profilul
« Răspunde #11 : Decembrie 17, 2010, 17:07:15 »

Care este raspunsul corect pentru :
3
8 12 -5
Memorat
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #12 : Decembrie 17, 2010, 17:12:56 »

Cod:
-9
Memorat
login
Strain


Karma: 3
Deconectat Deconectat

Mesaje: 4



Vezi Profilul
« Răspunde #13 : Decembrie 17, 2010, 17:24:35 »

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).
Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #14 : Decembrie 17, 2010, 18:14:53 »

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

Am zis Mr. Green
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #15 : Decembrie 17, 2010, 18:20:09 »

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 .
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines