10381 - The Rock

All about problems in Volume 103. 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
Jucovschi Constantin
New poster
Posts: 9
Joined: Sat Oct 26, 2002 6:30 pm

10381 - The Rock

Post by Jucovschi Constantin » Fri Nov 15, 2002 6:20 pm

Hi. When I submit my program it gets WA. Can somebody check whether my program gives the correct answer for the following tests? Are there any tricky tests? Id appreciate any tests for checking my program

Code: Select all

3
5 18
X..#.#............
.#.....##..#....#.
..#..#.#..#.#..#..
.#.##.##.#...##...
.....E............

8 8
E.......
###.###.
........
.###.###
........
#######.
........
X#######

10 10
E.........
..........
..........
..........
..........
..........
..........
..........
..........
.........X


My outputs:
33
29
18
Thanks in advance

jingye
New poster
Posts: 21
Joined: Sat Sep 07, 2002 5:28 am

Post by jingye » Fri Nov 15, 2002 7:33 pm

sigh. I get the same results as you. My program is WA also, though. Second test case will not occur because there are not two disjoint paths.

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

Post by Yarin » Mon Nov 18, 2002 8:28 pm

The result of the first and last input is correct, but the second one is not a valid input. If your program actually gets an answer for that in any case, it's a bit strange, it should be infinite or something in that case.

There are no tricks in the problem nor the input really.

jingye
New poster
Posts: 21
Joined: Sat Sep 07, 2002 5:28 am

Post by jingye » Thu Nov 21, 2002 1:16 am

Finally got accepted.
I thought E stood for exit, lol.

To Jucovschi Constantin: My program will also output 29 for the second test case, so I guess we use the same method.

Jucovschi Constantin
New poster
Posts: 9
Joined: Sat Oct 26, 2002 6:30 pm

Post by Jucovschi Constantin » Wed Nov 27, 2002 7:23 pm

I tried to get my program accepted but I couldnt.

I will write my idea, maybe it is wrong.

Consider the path consists of positions a1, a2, a3, .. an with a1=entrance. Suppose we delete position ai (it is the unknown wall) we have to reconstruct the path as a1, a2, a3 .. a(i-1) b1 b2 .. an. Sure b1, b2, .., an has to be the minimal path to connect a(i-1) and an with assumption that ai is a wall.

With F(i) we denote the length of the path that was reconstructed according the principle above.

The cost of a path is defined as max(F(i), i=1..n)

Let Q(x,y) be the minimal cost of all paths connecting the entrance with the position (x,y). |Q(x,y)| be the length of the path that gives this minimal cost.

Now if we take a neighbor position of (x,y), let it be (x1, y1). We can calculate the Q(x1,y1) = max(Q(x,y), |Q(x,y)|+minimal distance from (x,y) to exit).

The real algorithm is like djikstras algorithm. It takes minimal Q(x,y). And then tries to update the neighbors as it was shown.

Q(exit.x, exit.y) will be the optimal result.

I think it should work.

jingye
New poster
Posts: 21
Joined: Sat Sep 07, 2002 5:28 am

Post by jingye » Mon Dec 02, 2002 5:42 pm

I use the exact same idea, except I begin Dijkstra from end and go to start. Maybe you can change your program, and try the opposite direction.

CC
New poster
Posts: 8
Joined: Tue Oct 14, 2003 5:02 am

Post by CC » Sat Sep 04, 2004 7:31 am

can somebody give me the results for the following test cases

Code: Select all

10

20 40
........................................
........................................
........................................
........................................
.............###.#.#.#..................
............#...#.#...#.................
...........#..#.#.....#.................
...........#.#.X#......#................
...........#..#....#..#.................
............#......#...#................
.............###.##...#.................
................#.#...#.................
................#.#.#.#.................
...............#...#...#................
..............#....#....#...............
..............#....#....................
.....................#..................
......................#.................
.#####################.###############..
...................E....................

21 40
........................................
........................................
........................................
........................................
.............###.#.#.#..................
............#...#.#...#.................
...........#..#.#.....#.................
...........#.#.X#......#................
...........#..#....#..#.................
............#......#...#................
.............###.##...#.................
................#.#...#.................
................#.#.#.#.................
...............#...#...#................
..............#....#....#...............
..............#....#....................
.....................#..................
......................#.................
..####################.###############..
........................................
...................E....................

8 8
..X.....
........
##.##...
........
##.##...
##.##...
........
..E.....
 
3 4
..X.
.##.
.E..

8 8
..X.....
........
##.##...
..#.....
##.##...
##.##...
........
..E.....
3 3
X..
...
..E
 
3 4
..X.
.#..
.E..
 
3 4
..X.
....
.E..

4 5
.....
.....
..#..
.E#X.

3 3
X..
.#.
..E

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

Post by Per » Sat Sep 04, 2004 5:13 pm

My solution says:

Code: Select all

96
79
15
11
15
4
5
3
10
8

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

WA

Post by Moha » Mon Sep 19, 2005 10:13 am

I got WA in this problem, in my algorithm, for each empty cell I compute the shortest path cost in which if I come to this cell from side i(0<=i<=3) and I see this cell is blocked, then I should change my way in order to not to go to this cell and sum of these two cost should be minimized. after computing all of these costs, I use a simple dijkstra to find the best path with changed updating rule. my code answer all of these posted test cases correctly but I got WA. can anybody help me or post some more test cases?

Post Reply

Return to “Volume 103 (10300-10399)”