10531 - Maze Statistics

[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!

[Miguel Angel]

Could you give me some advice on how to calculate the probabilities??

[gush]

Per, could you please tell us how to solve this problem efficiently? I can't avoid TLE.

[..]

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

[Per]

The case I originally failed to handle was:

Code: Select all

1
0.5

[..]

Oh yes, my program misses this case, thanks Per

[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?

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

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