10913  Walking on a Grid
Moderator: Board moderators
dp
yes, it's DP
time complexity is about o(k * n^2)
Hint :
think when there is no rule that :
You can step on at most k negative integers from source to destination.
then you'll get DP algorithm,
and add this rule to your algorithm.
it will be not difficult.
time complexity is about o(k * n^2)
Hint :
think when there is no rule that :
You can step on at most k negative integers from source to destination.
then you'll get DP algorithm,
and add this rule to your algorithm.
it will be not difficult.
Sorry For My Poor English..
 Martin Macko
 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
Re: dp
My time complexity is O(kn^2), too. And the memory complexity is O(kn).Anonymous wrote:Are you sure about o(k * n^2) ?wook wrote:yes, it's DP
time complexity is about o(k * n^2)
My algo takes o(k * n^3). And work fast enough.
 Martin Macko
 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
 Martin Macko
 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)

 Experienced poster
 Posts: 161
 Joined: Tue Oct 25, 2005 8:38 pm
 Location: buet, dhaka, bangladesh
hi,
i cannot make a way to use DP in this problem. if you anyone describe how to implement DP here, i will be greatly helped. btw, can this problem be solved within time limit using dfs?
thanks in advance...
i cannot make a way to use DP in this problem. if you anyone describe how to implement DP here, i will be greatly helped. btw, can this problem be solved within time limit using dfs?
thanks in advance...
ishtiak zaman

the world is nothing but a good program, and we are all some instances of the program

the world is nothing but a good program, and we are all some instances of the program

 New poster
 Posts: 8
 Joined: Thu Jul 15, 2004 3:52 pm
 Location: Russia, Cherepovets
I used following DPalgorithm:ayon wrote:hi,
i cannot make a way to use DP in this problem. if you anyone describe how to implement DP here, i will be greatly helped. btw, can this problem be solved within time limit using dfs?
thanks in advance...
In cell t[i,j,g] save the maximum sum of integers of the path to cell(i,j), g is a count negative integer in the sum.
1.) As we start at cell (1,1), in all cells of first row we can arrive from left only. So, t[1,i,g] = t[1,i1,g]+m[1,i] if m[1,i] >= 0 else t[1,i,g+1] = t[1,i1,g]+m[1,i].
2.) Then for all row from 2 to n do:
 move down from row (i1) to row i
if m[i,j] >= 0 then t[i,j,g] = t[i1,j,g]+m[i,j]
else t[i,j,g] = t[i1,j,g1]+m[i,j]
 buf1[j,g] = buf2[j,g] = t[i,j,g]
 move from cell(i,1) to cell (i,n) try to maximize the result in buf1:
if (m[i,j] >= 0) then buf1[j,g] = max(buf1[j,g],buf1[j1,g]+m[i,j]) else buf1[j,g] = max(buf1[j,g],buf1[j1,g1]+m[i,j])
 also move from cell(i,n) to cell (1,n) correct buf2
 t[i,j,g] = max(t[i,j,g],buf1[j,g],buf2[j,g]);
3.) the maximum sum of integers of the path is max(t[n,n,g]) where 0<=g<=k.

 New poster
 Posts: 8
 Joined: Thu Jul 15, 2004 3:52 pm
 Location: Russia, Cherepovets
Try this input:L I M O N wrote:Someone pls send some critical data, i m getting WA again and again. i use DP.
Thx in Advace.
L I M O N
Code: Select all
1 0
1
1 0
1
1 1
1
3 0
1 1 1
1 1 1
1 1 1
4 0
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
4 1
1 1 1 1
1 1 1 1
10 1 5 1
1 1 1 1
3 5
1 1 1
1 1 1
1 1 1
3 4
1 1 1
1 1 1
1 1 1
5 2
2 1 10 3 13
5 4 3 2 1
100 2 3 43 17
24 92 40 14 40
100 100 1 1 1
0 0
Code: Select all
Case 1: 1
Case 2: impossible
Case 3: 1
Case 4: 9
Case 5: 13
Case 6: 14
Case 7: 5
Case 8: impossible
Case 9: 280