295 - Fatman

All about problems in Volume 2. 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
..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

295 - Fatman

Post by .. » Fri Oct 19, 2007 5:39 pm

Could anyone kindly give some test case?

I have no idea if my algorithm ok. Consider the sample input:
1
8 5
8
2 1
1 3
3 2
4 4
5 3
6 4
7 2
7 1
For each combination of obstacle(along x-axis), I consider a "tunnel" that is formed by "ceiling" and "floor", which are both series of segment.
Say ceiling is "(1,3) (2, 5) (3, 5) (4, 4) ..." and floor is "(1, 0) (2, 1) (3, 2) (4, 0)...." Then I output the minimum pairwise of the vertex forming the tunnel.
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.

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Sat Oct 27, 2007 11:51 pm

If I understood your algorithm correctly, it will give wrong answer to both of these cases:

Code: Select all

2
9 6
18
1 2
2 2
3 2
4 2
5 2
6 2
1 3
1 4
1 5
8 1
8 2
8 3
8 4
7 4
6 4
5 4
4 4
3 4
4 10
12
1 4
1 5
1 6
1 7
1 8
1 9
3 1
3 2
3 3
3 4
3 5
3 6
The first case is a zigzag maze where the man must go right, down, left, down, right. The second case is a passage with two "walls" close to each other, with wide openings. Your algorithm would return 1 and 4 for these tests, while the correct answer is 2.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Sun Oct 28, 2007 5:22 am

oh yes :o
I completely forget this is a maze....
I need to find a new algorithm, thanks a lot.
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.

gt1404
New poster
Posts: 6
Joined: Sat Dec 26, 2009 10:16 am

Re: 295 Fatman

Post by gt1404 » Thu Aug 19, 2010 7:28 pm

Anybody have any test cases. Everything I have checks out with the solution by hand including mazes and L=0, W=0 cases. I'm failing around the 1 second mark, did anyone have an issue with rounding here???

Thanks in advance
-gt

Post Reply

Return to “Volume 2 (200-299)”