infoarena

Aici puteţi discuta despre problema Joc (http://infoarena.ro/problema/joc).

Uite ca am si eu o nelamurire la aceasta problema.
Prin "diferenta de scor" se intelege cumva modul? In cazul in care se intelege modul, problema a devenit brust MULT mai grea, sincer eu nu am nici o idee.

Diferenta de scor inseamna "Scor Gicu - Scor Nicu"

Ar trebui sa pui asta in enunt. Really.

Am facut o solutie O(N*M) cu programare dinamica... si nu stiu ce are, ca iau doar 30 de puncte... si rationamentul meu pare infailibil  :D
Am o matrice de BEST de NxM , A e aia citita din fisier... in principiu e ceva de genu best[j]=a[j]-MAX(best[i-1][j],best[j-1])... si asta in 2 for-uri, mai intai unu pt linii si apoi pt coloane... ce gresesc?  :cry:

Se ofera careva care a facut-o sa se uite pe sursa mea? Merg doar cazurile 6, 8, 9... restul wrong answer.

Daca se ofera careva voluntar sa se uite pe sursa mea, sa-mi lase mailu pe private or smth... multumesc anticipat.  :D

Ziceti-mi si mie cat da pe  :

5 7
1  1 -3  1  3   1  2
2  1  3  4  0   5  3
3 -1 -2  0  4  -1  4
2  3  4  5  6   2  3
3  1  2  1  2   1  2

si pe :
4 6
 2  1  3   4  0   5
 3 -1 -2  0   4 -1
-1 -2 -3 -4 -5 -6
 1  2  3  4   5  6
poate ma prind ce-am gresit.

Multumesc anticipat! ](*,)

3 2 6 si 3 1 6

10X domino!

Buna :D , toate testele care le-am dat la joc mie mi-au iesit corect...
Iar la evaluare am 1..9 gresit si 10 time limit exceeded.
Am o solutie inspirata de la Druid...
Am o matrice Sol,A,Max
in Sol memorez solutia , A este matricea din fisier iar in Max retin valoarea maxima din Sol din dreptunghiul (1,1) si (i,j)...
sol[i,j]:=a[i,j]-max[i,j].
Si cam atat ar fi in mare...
NU cred ca ideea mea de rezolvare ii gresita , ci poate am ceva gresit in implementare
Daca ai putea pls sa-mi dai un test mai mic sa vad unde naiba gresesc !
#-o.

NU imi dau seama nicicum unde gresesc  :(
daca se poate uita cineva peste sursa mea...
NU o sa mai postesz si partea de citire si afisare...

function maxim(a,b:integer):integer;
begin
maxim:=(a+b+abs(a-b)) div 2;
end;

procedure calcul;
begin
fillchar(sol,sizeof(sol),0);
Vmax:=-1000;i:=1;j:=1;
for i:=1 to n do
    for j:=1 to m do
        begin
         sol[i,j]:=a[i,j]-max[i,j];
         max[i,j]:=maxim(max[i,j],sol[i,j]);
         max[i,j+1]:=max[i,j];
         max[i+1,j]:=max[i,j];
         if Vmax<sol[i,j] then
            begin
             Vmax:=sol[i,j];
             si:=i;sj:=j;
            end;
        end;
end;

Chiar nu pot sa-mi dau seama unde gresesc...Eventual daca cineva imi gaseste un test in care programul meu greseste(eu n-am reusit sa gasesc)

                   Multumesc anticipat

Gata am gasit care e problema...  :D
NU ii corecta partea cu max...Am facut-o altfel , ii mai lenta , iau 60 de puncte pe ea, ultimele teste time limit exceeded.

incerca sa nu mai  folosesti functii cum ar fi  abs, mai bine implementeazo singur , pt ca mananca timp,   asa am patit eu pe  .campion  cu  functia  sqrt, (TLE)

Nu stiam ca abs ar manca mult timp.
Dar cum spui tu sa o implementez  cu IF ?
Nu ii mai lenta asa !?
Thx pentru observatie :P

Imi poate da cineva un contraexemplu pentru algortimul dat de druid? Mie mi se pare corect, dar totusi iau doar 30 puncte pe el

Ai grija ca trebuie sa iei maximul din dreptunghiul lui (1,1) (i,j) dar sa nu incluzi si pe sol[j] deci mai bine iei maximul din (1,1) (i-1,j)  si maximul din (1,1) (i,j-1)

Poti sa-mi explici ce ai vrut sa zici, ca n-am reusit sa inteleg. Scuze... :-s

Am vazut aiurea ceva in postul anterior, dar nu stiu ce face in codul asta:
max[i,j+1]:=max[i,j];
max[i+1,j]:=max[i,j];
 Nu ar trebui sa faca un if cand actualizeaza max[i,j+1] si max[i+1,j]?

pe solutia urmatoare...

Iau 30 p... Daca , calculez max babeste si nu iau punctul [i,j] iau
60p ,ultimele 4 teste nu se incadreaza in timp...
Pentru solutia de 30 p nu determina totdeauna max corect dar nu stiu de
ce...  :|

Edit:

Cosmin: probabil ca te refereai la mine...
Ce am scris eu acolo era o prostie , luam 0 p pe ea... :lol:

Bah ti-am zis si dincolo sa folosesti "[code]" ca nu se intelege nimic.

Ii ok acuma!?  :wink:

Da, super! :)

totusi.. eu nu sunt lamurit deloc.. care e pana la urma greseala in algoritmul prezentat mai sus de druid.. poate cineva care sa-mi dea vreo indicatie?

multumesc.

Incearca sa dai niste  teste cu valori negative, eu acolo am avut greseala si dupa ce am sesizat-o am luat 100 p.
Hope it help's ...

da.. aici era greseala. mersi

pentru a calcula maximul folosesc urmatoarea secventa:

imi poate spune cineva ce am gresit pentru ca iau numai 30 de puncte restul WA

Eu luam 30 pct pentru ca gresisem initializarea matricei

Nu pricep cum obtine diferenta 3..
Gicu ia 5 (1,6), Nelu 4 (1,4) => dif=1;
Gicu ia 3 (1,3), Nelu 2 (1,1)=> dif=2;
si se termina jocul...

ceea ce e totuna cu: Gicu ia 2(1,1)... si se termina.. e aceasi diferenta.. avand in vedere ca amandoi joaca optim, nu ma prind ce nu am inteles in exemplul respectiv...

diferenta 3 se obtine astfel: Gicu ia 5 (1,6), Nelu ia 4 (1,4), Gicu ia 2 (1,1). 5+2-4 = 3
prima linie a matricii este si exemplul dat de mircea, al carui raspuns este tot 3 1 6.

LE: strategia dupa care ai incercat sa rezolvi exemplul de mai sus e greedy. problema se rezolva prin programare dinamica (cel putin asa am rezolvat-o eu)

Nu inteleg deloc de ce nu merge testul 8. Algoritmul meu memoreaza in sol[ i ][ j ] - maximul  pana la (i,j) (desigur memorez undeva solutia ca sa fie pe lina si coloana potrivita). sol[ i ][ j ]=max(sol[ i-1 ][ j ],sol[ i ][ j-1 ],a[ i ][ j ]-sol[ i ][ j-1 ],a[ i ][ j ]-sol[ i-1 ][ j ]).
Teoretic ar trebui sa mearga perfect.
Ba chiar arata si greseala din exemplul lui domino (vad ca nu a mentionat nimeni, pentru primul test solutia e 3 2 4 nu 3 2 6).

Chiar nu am nici o idee de rezolvare :shock:,ma puteti ajuta cu niste indicatii?? :-k

Chiar esti orb ? Pe bune acum, rezolvarea este exact cu un post mai sus, si minune e si corecta  :shock:.

Cat va da pentru testul respectiv?
1 2
-5 -5

0 1 2

Intuieste cineva ce are testul 8 ? Solutia mea e asemanatoare cu cea descrisa de usurelu catalin .

 @ Ursuletul Catalin: pentru acel test a lui Domino,raspunsul este chiar 3 2 6  :-'....

...


Iau 80 de puncte cu WA pe 6 si 9, si am ajuns la concluzia ca este din cauza maximului. Asta este bucata unde lucrez cu maximul... Nu imi dau seama de greseala nicidecum. Sa fie altceva?

Va rog foarte frumos sa mentionati in restrictiile problemei ca diferenta de scor inseamna scor Gicu - scor Nicu. Cuvantul "diferenta" are o alta semnificatie decat cea pe care o are in enunt. Am pierdut foarte mult timp si nu as vrea sa piarda si altii.

Diferenta (http://dexonline.ro/definitie/diferen%C8%9B%C4%83): vezi prima definitie, semnificatia 2.

Citeste primele doua comentarii din acest topic. Enuntul este destul de clar.

Va rog, ar putea posta cineva o mica explicatie a relatiei de reucrenta? d[ i][j] = diferenta maximace poate fi obtinuta in dreptunghiul incadrat de pozitia (1,1) si (i,j). Eu asa m-am gandit, dar nu ma prind cum sa continui. Am vazutca intr-adevar, si altii au facut asa. Mi-ar prinde bine un hint. multumesc in avans!

Ok...nu pot sa trec peste 60 de punte orice as face. Ma poate ajuta cineva?

Nevermind....era o greseala stupida.... ](*,) ](*,) ](*,)

Problema asta ma dispera. Am facut cu programare dinamica si tot imi da 70 de puncte, cu testele 6, 8, 9 WA. Uitati codul:

Cod:

#include <bits/stdc++.h>

#define Max 1004

FILE *fin, *fout;
int N, M;
int a[Max][Max];
int maxi[Max][Max], sol[Max][Max];

inline int smax(int a, int b)  {
    if(a > b)
        return a;

    return b;
}


int main()  {
    fin = fopen("joc.in", "r");
    fout = fopen("joc.out", "w");

    int s;

    fscanf(fin, "%d%d", &N, &M);

    for(int i = 1;i <= N;i++)
        for(int j = 1;j <= M;j++)
            fscanf(fin, "%d", &a[j]);
    int ri, rj;

    s = a[1][1];
    ri = 1, rj = 1, maxi[1][1] = a[1][1];
    sol[1][1] = a[1][1];
    maxi[1][2] = a[1][1];
    maxi[2][1] = a[1][1];


    for(int i = 1;i <= N;i++)
        for(int j = 1;j <= M;j++)  {
            if(i == 1 && j == 1)
                continue;
            sol[j] = a[j] - maxi[j];
            maxi[j] = smax(maxi[j], sol[j]);
            maxi[j + 1] = maxi[j];
            maxi[i + 1][j] = maxi[j];
            maxi[i + 1][j + 1] = maxi[j];
            if(sol[j] > s)
                s = sol[j], ri = i, rj = j;
        }

    fprintf(fout, "%d %d %d", s, ri, rj);

    fclose(fin);
    fclose(fout);

    return 0;
}

Later edit:

Am luat 100p. Am refacut dinamica si a mers :)

De ce nu e diferența maximă 10? Rețin o matrice smax[2][ i][j] , în care rețin soluția maximă pe care o obțin având ultimul jucător Gicu (pt. rândul 0) sau Nicu (pt. rândul 1). Gicu poate lua jetoanele de valoare 5, 4 și 2, iar Nicu cele de valoare 0 și 1.

Pe cazul din exemplu se intampla ceea ce este scris la explicatii, mai jos de enunt.

Ideea este ca primul jucator vrea sa maximizeze diferenta, iar cel de-al doilea urmareste sa o minimizeze, asta inseamna ca "amandoi joaca optim". ;)

Daca am matricea 6 1 2 3 4 7 Gicu alege 7 sau 6 ????

Never mind, am inteles!