## 10531 - Maze Statistics

Moderator: Board moderators

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

### 10531 - Maze Statistics

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

Miguel Angel
Learning poster
Posts: 60
Joined: Tue Aug 13, 2002 2:39 am
Location: Mexico
Could you give me some advice on how to calculate the probabilities??
Miguel & Marina

gush
New poster
Posts: 13
Joined: Tue Oct 14, 2003 12:47 pm
Per, could you please tell us how to solve this problem efficiently? I can't avoid TLE.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
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:
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???
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
The case I originally failed to handle was:

Code: Select all

``````1
0.5``````

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
Oh yes, my program misses this case, thanks Per
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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.