11487 - Gathering food

Moderator: Board moderators

11487 - Gathering food

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][i][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

andmej
Experienced poster

Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 11487 - Gathering food

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

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

Re: 11487 - Gathering food

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

Posts: 45
Joined: Sun Jun 26, 2005 6:21 am

Re: 11487 - Gathering food

Try these
Code: Select all
`3A.......B10A..................................................................................................B1A3ABCDEF...6ABCDEFGHIJKLMNOPQRSTUVWXYZ####......3..A.B.C..3ABC...###3....A....2ACDB2ACBD5A....####...B...####C.DE.2A..B2A##B0`

Code: Select all
`Case 1: 4 6Case 2: 18 7746Case 3: 0 1Case 4: 7 1Case 5: 45 1Case 6: 4 4Case 7: 2 1Case 8: 0 1Case 9: ImpossibleCase 10: 4 1Case 11: 15 1Case 12: 2 2Case 13: Impossible`
FAQ
Learning poster

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

Re: 11487 - Gathering food

Thx I got AC, my BFS doesn't consider if food is already taken than you can pass that point
Code: Select all
`3ABCDEF...`
New poster

Posts: 45
Joined: Sun Jun 26, 2005 6:21 am

Re: 11487 - Gathering food

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............
Articuno
Learning poster

Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm

Re: 11487 - Gathering food

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.

sohel
Guru

Posts: 862
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

Re: 11487 - Gathering food

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);         }`

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............
Articuno
Learning poster

Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm

Re: 11487 - Gathering food

try these cases:
Input
Code: Select all
`10D........B................................................................................A........C10D#..##...B..........###..####...............E.....###....##..............###..............A........C10........................................ACB.........................................................0`

Output
Code: Select all
`Case 1: 45 2429Case 2: 53 12876Case 3: 5 2`

sohel
Guru

Posts: 862
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

Re: 11487 - Gathering food

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............
Articuno
Learning poster

Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm

Re: 11487 - Gathering food

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.

sohel
Guru

Posts: 862
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

Re: 11487 - Gathering food

Thanks a lot Sohel vai. Thanks a lot for your suggestion. Got AC
May be tomorrow is a better day............
Articuno
Learning poster

Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm