Page 1 of 1
11487 - Gathering Food
Posted: Sun Sep 14, 2008 6:46 pm
by andmej
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?
Re: 11487 - Gathering food
Posted: Sun Sep 14, 2008 11:03 pm
by Monsoon
do bfs starting from 'A', then from 'B', ....
you can easily put counting number of shortest paths in bfs function
Re: 11487 - Gathering food
Posted: Mon Sep 15, 2008 3:25 pm
by marcadian
I'm try counting the way in the BFS, but it gets WA, can anyone give me test case ?Thx
Re: 11487 - Gathering food
Posted: Mon Sep 15, 2008 4:31 pm
by FAQ
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
Re: 11487 - Gathering food
Posted: Mon Sep 15, 2008 7:19 pm
by marcadian
Thx I got AC, my BFS doesn't consider if food is already taken than you can pass that point
Re: 11487 - Gathering food
Posted: Mon Dec 01, 2008 11:02 am
by Articuno
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:
Re: 11487 - Gathering food
Posted: Wed Dec 03, 2008 11:00 am
by sohel
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.
Re: 11487 - Gathering food
Posted: Wed Dec 03, 2008 12:14 pm
by Articuno
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?
Re: 11487 - Gathering food
Posted: Wed Dec 03, 2008 4:41 pm
by sohel
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
Re: 11487 - Gathering food
Posted: Wed Dec 03, 2008 6:59 pm
by Articuno
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.
Re: 11487 - Gathering food
Posted: Thu Dec 04, 2008 9:04 am
by sohel
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.
Re: 11487 - Gathering food
Posted: Thu Dec 04, 2008 6:18 pm
by Articuno
Thanks a lot Sohel vai. Thanks a lot for your suggestion. Got AC