## 10913 - Walking on a Grid

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

### 10913 - Walking on a Grid

dp?

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

### 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.
Sorry For My Poor English..

liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am
ac now
Thank you

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
Previous post is mine.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

### Re: dp

Anonymous wrote:
wook wrote:yes, it's DP

time complexity is about o(k * n^2)
Are you sure about o(k * n^2) ?

My algo takes o(k * n^3). And work fast enough.
My time complexity is O(kn^2), too. And the memory complexity is O(kn).

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
Thx, I optimized my algo. Now it's O(k * n^2) too.

However running time didn't improved much.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
kp wrote:Thx, I optimized my algo. Now it's O(k * n^2) too.

However running time didn't improved much.
It would have been more significiant if n would be much bigger than 75.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Can someone post some example cases? Thanks!

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
Larry wrote:Can someone post some example cases? Thanks!
I'm lazy to generate any inputs , but if you post some here I can generate the correct answers for you.

ayon
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?
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

Andrey Grigorov
New poster
Posts: 8
Joined: Thu Jul 15, 2004 3:52 pm
Location: Russia, Cherepovets
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?
I used following DP-algorithm:
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,i-1,g]+m[1,i] if m[1,i] >= 0 else t[1,i,g+1] = t[1,i-1,g]+m[1,i].
2.) Then for all row from 2 to n do:
- move down from row (i-1) to row i
if m[i,j] >= 0 then t[i,j,g] = t[i-1,j,g]+m[i,j]
else t[i,j,g] = t[i-1,j,g-1]+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[j-1,g]+m[i,j]) else buf1[j,g] = max(buf1[j,g],buf1[j-1,g-1]+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.

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh
thank you very much Andrey, now i understand clearly how to use DP here. your explaination is very clear and fine. thanks again for the help
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Contact:
Someone pls send some critical data, i m getting WA again and again. i use DP.

L I M O N

Andrey Grigorov
New poster
Posts: 8
Joined: Thu Jul 15, 2004 3:52 pm
Location: Russia, Cherepovets
L I M O N wrote:Someone pls send some critical data, i m getting WA again and again. i use DP.

L I M O N
Try this input:

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
``````
Output:

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

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Contact:
my outputs :

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

but Same result, WA.
do u use "long long" data type ? i also use this type.

pls send more data

L I M O N