Page 1 of 1
10531 - Maze Statistics
Posted: Mon Aug 04, 2003 9:24 pm
by Per
I'm getting WA on this problem. Could somebody check this I/O and tell me if I'm way off or if I just have precision errors?
Input:
Code: Select all
4
3 3
0.5 0.5 0.5
0.5 1.0 0.5
0.2 0.5 0.5
3 3
0.5 0.5 0.5
0.5 0.9 0.5
0.2 0.5 0.5
5 5
0.5 0.5 0.5 0.5 0.5
0.5 0.5 0.5 0.5 0.5
0.5 0.5 0.5 0.5 0.5
0.5 0.5 0.5 0.5 0.5
0.5 0.5 0.5 0.5 0.5
5 6
0.5 0.5 0.5 0.5 0.5 0.5
0.5 0.5 0.5 0.5 0.5 0.5
0.5 0.5 0.0 1.0 0.5 0.5
0.5 0.5 0.5 0.5 0.5 0.5
0.5 0.5 0.5 0.5 0.5 0.5
Output:
Code: Select all
0.000000 0.333333 0.333333
0.208333 1.000000 0.333333
0.083333 0.208333 0.000000
0.000000 0.333333 0.362069
0.229885 0.827586 0.333333
0.103448 0.229885 0.000000
0.000000 0.306323 0.405105 0.460020 0.487886
0.306323 0.326223 0.363506 0.415657 0.460020
0.405105 0.363506 0.347423 0.363506 0.405105
0.460020 0.415657 0.363506 0.326223 0.306323
0.487886 0.460020 0.405105 0.306323 0.000000
0.000000 0.297131 0.387883 0.442577 0.464531 0.487493
0.316706 0.338355 0.330075 0.418980 0.387451 0.461218
0.415218 0.382289 0.000000 1.000000 0.426257 0.432297
0.469424 0.464337 0.238489 0.323881 0.326913 0.340870
0.491602 0.464554 0.405177 0.344487 0.259860 0.000000
Thanks in advance!
Posted: Thu Aug 07, 2003 11:30 pm
by Miguel Angel
Could you give me some advice on how to calculate the probabilities??
Posted: Wed Oct 15, 2003 7:56 am
by gush
Per, could you please tell us how to solve this problem efficiently? I can't avoid TLE.
Posted: Sat Nov 12, 2005 5:30 pm
by ..
Could anyone got AC help verify this:
There will always be a non-zero probability that a generated maze will be solvable.
I write a program that do this thing:
1. read case
2. make a maze, a sqaure has berrier on it only if the input probability is 1.0
3. use BFS to find a route from top left to bottom right
My program found that there is no route on this maze......
Could anyone verify this? Do I make a silly mistake???
Posted: Sun Nov 13, 2005 9:58 pm
by Per
The case I originally failed to handle was:
Posted: Mon Nov 14, 2005 8:04 am
by ..
Oh yes, my program misses this case, thanks Per
Posted: Sat Oct 21, 2006 7:03 pm
by little joey
Hmm. Looks like requests for a hint are not honoured for this problem... but I'll give it a try.
I've been struggling with this one for over three years now, and I'm getting nowhere. The only thing I can think of is enumerating all possible states and then check if they're connected. This gives me the correct answers, but way too slow. There are some minor optimizations, but none enough to get there in time.
Anyone care to drop a hint or two here?
Posted: Sat Oct 21, 2006 8:25 pm
by mf
I've used dynamic programming. Subproblems look like this: given that I've generated top the k rows, and knowing which of the cells of the k-th row are connected between them by paths in upper rows (there are not too much possible patterns here), with what probability can I generate the remaining rows such that the maze will be solvable?
There was recently a similar problem on TopCoder -
CheapestIsland, you might find its
analysis very useful.
Posted: Sat Oct 21, 2006 10:03 pm
by little joey
Thanks! I needed that hint. I'll try to implement it tomorrow.
UPDATE:
Now I finally solved it and learned something new about DP which can be useful for solving other problems too! Thanks again, mf.