016 Joc

[•fluffy]

Aici puteţi discuta despre problema Joc.

[•fluffy]

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.

[•domino]

Diferenta de scor inseamna "Scor Gicu - Scor Nicu"

[•fluffy]

Ar trebui sa pui asta in enunt. Really.

[•druid]

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

[•sarabogdan]

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!

[•domino]

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

[•sarabogdan]

10X domino!

[•dobre]

Buna , 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 !
.

[•dobre]

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

[•dobre]

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

[•Matrix]

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)

[•dobre]

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

[•bogdan2412]

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

[•Cosmin]

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)

[•bogdan2412]

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

[•Cosmin]

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]?

[•dobre]

pe solutia urmatoare...

Cod:

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]:=maxim(max[i,j],max[i,j+1]);
         max[i+1,j]:=maxim(max[i,j],max[i+1,j]);
         if Vmax<sol[i,j] then
            begin
             Vmax:=sol[i,j];
             si:=i;sj:=j;
            end;
        end;

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:

[•Cosmin]

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

[•dobre]

Ii ok acuma!?  

[•Cosmin]

Da, super!

[u-92]

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.

[•dobre]

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

[u-92]

da.. aici era greseala. mersi

[•Dorin]

pentru a calcula maximul folosesc urmatoarea secventa:

Cod:

max = -32001;
if(b[i-1][j] > max)
	max = b[i-1][j];

if(b[i][j-1] > max)
	max = b[i][j-1];

if(c[i-1][j] > max)
	max = c[i-1][j];

if(c[i][j-1] > max)
	max = c[i][j-1];

b[i][j] = max;

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