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

Post by liulike » Sat Sep 24, 2005 5:13 am

dp? :o

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

dp

Post by wook » Sat Sep 24, 2005 5:21 am

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

Post by liulike » Sat Sep 24, 2005 5:13 pm

ac now
Thank you :)

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

Post by kp » Sun Sep 25, 2005 2:40 pm

Crazy autologin :evil: :)
Previous post is mine.

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

Re: dp

Post by Martin Macko » Sun Sep 25, 2005 10:58 pm

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

Post by kp » Mon Sep 26, 2005 1:05 am

Thx, I optimized my algo. Now it's O(k * n^2) too.

However running time didn't improved much.

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

Post by Martin Macko » Mon Sep 26, 2005 2:16 am

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:

Post by Larry » Tue Oct 04, 2005 10:14 am

Can someone post some example cases? Thanks!

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

Post by Martin Macko » Sat Dec 10, 2005 10:43 pm

Larry wrote:Can someone post some example cases? Thanks!
I'm lazy to generate any inputs :oops:, 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

Post by ayon » Tue Jan 03, 2006 8:52 pm

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

Post by Andrey Grigorov » Wed Jan 04, 2006 11:57 am

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

Post by ayon » Wed Jan 04, 2006 2:34 pm

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
Location: Dhaka, Bangladesh
Contact:

Post by L I M O N » Wed Jan 04, 2006 10:18 pm

Someone pls send some critical data, i m getting WA again and again. i use DP.

Thx in Advace.

L I M O N

Andrey Grigorov
New poster
Posts: 8
Joined: Thu Jul 15, 2004 3:52 pm
Location: Russia, Cherepovets

Post by Andrey Grigorov » Wed Jan 04, 2006 11:31 pm

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
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
Location: Dhaka, Bangladesh
Contact:

Post by L I M O N » Wed Jan 04, 2006 11:45 pm

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

Post Reply

Return to “Volume 109 (10900-10999)”