10531 - Maze Statistics

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10531 - Maze Statistics

Post by Per » Mon Aug 04, 2003 9:24 pm

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
Learning poster
Posts: 60
Joined: Tue Aug 13, 2002 2:39 am
Location: Mexico

Post by Miguel Angel » Thu Aug 07, 2003 11:30 pm

Could you give me some advice on how to calculate the probabilities?? :oops:
:D Miguel & Marina :D

gush
New poster
Posts: 13
Joined: Tue Oct 14, 2003 12:47 pm

Post by gush » Wed Oct 15, 2003 7:56 am

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

Post by .. » Sat Nov 12, 2005 5:30 pm

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???
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    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

Post by Per » Sun Nov 13, 2005 9:58 pm

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

Post by .. » Mon Nov 14, 2005 8:04 am

Oh yes, my program misses this case, thanks Per :D
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sat Oct 21, 2006 7:03 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:

Post by mf » Sat Oct 21, 2006 8:25 pm

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sat Oct 21, 2006 10:03 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.

Post Reply

Return to “Volume 105 (10500-10599)”