11487 - Gathering Food

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

Moderator: Board moderators

Post Reply
User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

11487 - Gathering Food

Post by andmej » Sun Sep 14, 2008 6:46 pm

During the contest, I solved this problem using BFS with state [i, j, food] where i = row, j = column and food = letter I'm trying to grab.
To count the number of shortests paths, I filled a table paths[len][j][food] = number of different paths of length "len" ending at state [i, j, food].

However, my solution is rather slow. I've seen some people ranked with times < 0.010. What's the fastest method to solve this problem?
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

Re: 11487 - Gathering food

Post by Monsoon » Sun Sep 14, 2008 11:03 pm

do bfs starting from 'A', then from 'B', ....
you can easily put counting number of shortest paths in bfs function

marcadian
New poster
Posts: 45
Joined: Sun Jun 26, 2005 6:21 am
Contact:

Re: 11487 - Gathering food

Post by marcadian » Mon Sep 15, 2008 3:25 pm

I'm try counting the way in the BFS, but it gets WA, can anyone give me test case ?Thx

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

Re: 11487 - Gathering food

Post by FAQ » Mon Sep 15, 2008 4:31 pm

Try these

Code: Select all

3
A..
...
..B
10
A.........
..........
..........
..........
..........
..........
..........
..........
..........
.........B
1
A
3
ABC
DEF
...
6
ABCDEF
GHIJKL
MNOPQR
STUVWX
YZ####
......
3
..A
.B.
C..
3
ABC
...
###
3
...
.A.
...
2
AC
DB
2
AC
BD
5
A....
####.
..B..
.####
C.DE.
2
A.
.B
2
A#
#B
0

Code: Select all

Case 1: 4 6
Case 2: 18 7746
Case 3: 0 1
Case 4: 7 1
Case 5: 45 1
Case 6: 4 4
Case 7: 2 1
Case 8: 0 1
Case 9: Impossible
Case 10: 4 1
Case 11: 15 1
Case 12: 2 2
Case 13: Impossible


marcadian
New poster
Posts: 45
Joined: Sun Jun 26, 2005 6:21 am
Contact:

Re: 11487 - Gathering food

Post by marcadian » Mon Sep 15, 2008 7:19 pm

Thx I got AC, my BFS doesn't consider if food is already taken than you can pass that point

Code: Select all

3
ABC
DEF
...

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 11487 - Gathering food

Post by Articuno » Mon Dec 01, 2008 11:02 am

Hi, i am new in programming. I have learned BFS and implemented it in this problem. My program is giving correct output for the test cases those are given here. but it is WA. I think there is a problem in counting the number of shortest paths and i am confused about my technique. Can anyone please check my code and tell me what is wrong. Please help me.......

Here is my code:

Code: Select all

Removed
Last edited by Articuno on Thu Dec 04, 2008 6:20 pm, edited 1 time in total.
May be tomorrow is a better day............ :)

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 11487 - Gathering food

Post by sohel » Wed Dec 03, 2008 11:00 am

a part of your code

Code: Select all

for(i=0;i<tp;i++)
            {
               ans1=ans1+totaldist[i];
            }
            ans2=1;
            for(i=0;i<tp;i++)
            {
               ans2=ans2*totalpath[i];
            }
            ans2=ans2%20437;
in the last line, ans2 can be very big and won't fit into integer data type and thus will lead to faulty outputs.
Try to do MOD after every operation.

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 11487 - Gathering food

Post by Articuno » Wed Dec 03, 2008 12:14 pm

I have changed that part of my code into this:

Code: Select all

else
			{
				ans1=0;
				for(i=0;i<tp;i++)
				{
					ans1=ans1+totaldist[i];
				}
				ans2=1;
				for(i=0;i<tp;i++)
				{
					ans2=(((ans2)%20437)*(totalpath[i]%20437))%20437;
				}
				ans2=ans2%20437;
				printf("Case %lld: %lld %lld\n",cas,ans1,ans2);
			}

:cry: But still it is WA. I had also changed the data type and used long long. But still..... WA.
Can you give me some critical test cases?
May be tomorrow is a better day............ :)

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 11487 - Gathering food

Post by sohel » Wed Dec 03, 2008 4:41 pm

try these cases:
Input

Code: Select all

10
D........B
..........
..........
..........
..........
..........
..........
..........
..........
A........C
10
D#..##...B
..........
###..####.
..........
....E.....
###....##.
..........
...###....
..........
A........C
10
..........
..........
..........
..........
ACB.......
..........
..........
..........
..........
..........
0
Output

Code: Select all

Case 1: 45 2429
Case 2: 53 12876
Case 3: 5 2

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 11487 - Gathering food

Post by Articuno » Wed Dec 03, 2008 6:59 pm

Thanks Sohel vai for your help. I think i have found my error. I can not figure out the way how to find the total number of distinct paths. Can you help me a little more. Please give me some hints about how to count the number of distinct paths. My program can count the shortest distance correctly but there is problem in counting the number of paths. Kindly give me some hints about the process as i am unable to figure it out. I have tried different approaches but all in vain. Thanks for ur help.
May be tomorrow is a better day............ :)

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 11487 - Gathering food

Post by sohel » Thu Dec 04, 2008 9:04 am

The total number of paths can be found by basic dynamic programming.
Suppose we have 4 letters {A B C D}.

Total Number of paths = TNP (for the sake of brevity)
Result = TNP(from A to B) * TNP(from B to C) * TNP(from C to D).

So basically, what we need is to find the total number of paths from a point to that of another.
Suppose are going from A to B and let the shortest path be equal to 10.
Lets make a move from A. If the shortest path from the new position to B is equal to 9, then that point must be a part of the path. You can use dp to memoize repeated states.

I suggest you solve some easy dynamic programming problems first, then you will be able to get a good grasp of this problem. :)

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 11487 - Gathering food

Post by Articuno » Thu Dec 04, 2008 6:18 pm

Thanks a lot Sohel vai. Thanks a lot for your suggestion. Got AC
May be tomorrow is a better day............ :)

Post Reply

Return to “Volume 114 (11400-11499)”