10605 - Mines For Diamonds

[Adrian Kuegel]

For those who already tried to solve this problem:

I made a mistake in my interpretation of the original problem statement. In the original problem it was allowed, that two mines are adjacent, like in this example:

Code: Select all

6 5
#####
#   #
# **#
# **#
#   #
#####


A solution would be:

Code: Select all

#####
#   #
# --#
# --#
#   #
#####


I thought that it is always invalid to have more than 2 adjacent grid squares that belong to a mine.

For example this is one of my test cases and my solution for it:

Code: Select all

10 10
##########
#........#
#..*.*...#
#...*....#
#..*..*..#
#...*....#
#..*.*...#
#........#
#........#
##########

20
##########
#..X.X...#
#..*.*...#
#...*X...#
#XX*..*XX#
#...*X...#
#..*.*...#
#..X.X...#
#..X.X...#
##########


Please tell me, what do you think? Shall I change the problem statement and the solution, or just clarify the "new" problem with more examples, or shall I add another problem that is like the original problem?

[Dominik Michniewski]

I don't try to write code to this problem , but I think that we should find minimal length of digged 'corridors', so first (with adjacent mines) example is correct for me.
I think that would be better to change solution
Adrian, what do you mean 'change problem statement' in case of changing solution ?

Best regards
DM

[Adrian Kuegel]

Thanks for your opinion.
What I meant by changing the problem statement: I would insert a remark that mines can go parallel, because this statement could be misleading:

so within a mine there may not be any grid square with more than two adjacent grid squares.

Well, if you know that mines can be parallel, this is no contradiction, because the grid squares of parallel mines are not adjacent. But perhaps it is better to make the problem statement clearer.

[Per]

Let me see if I understood this correctly: in the current version of the problem, your first input has no solution, and in the original version of the problem, a solution to your second case would be something like:

Code: Select all

17
##########
#..X.....#
#..*X*...#
#..X*X...#
#..*..*XX#
#..X*X...#
#..*X*...#
#........#
#........#
##########


(maybe there's an even better solution which I don't see...)

Did I understand correctly?

I think that as long as the judge I/O is consistent with the problem statement, it could be kept as it is. Besides, the problem feels more difficult this way.

Perhaps the footer of the problem statement should be changed slightly to say that the problem is inspired by (or a variant of) a German National Olympiad problem or something like that.

[Adrian Kuegel]

Per, it is exactly as you said. First input has no solution with my first program, and I wrote now another program for the original problem and it outputs a solution of length 17 for the 2nd test case.
But I fear the problem statement like it is now is not very clear, so I have to clarify which problem should be solved (when I read the problem statement now I think that there are reasons to understand it in both ways).

[Per]

Hmm, yes, now that you mention it, I can see that the phrase about adjacent grid squares can be interpreted differently, particularly since it is a clarification about how mines cannot branch out and that it says "within a mine".

If I may do a 180 degree turnabout, I think the problem as it stands now definitely describes the original problem (except that there could be different interpretations about whether mines may go zig-zag)

As you're the only one who has solved the problem, I don't think there's any harm in changing the statement. On the other hand, for the same reason there is no harm in fixing the I/O either.

The only reason I see for changing the problem instead of the I/O is that the problem seems harder this way -- but I guess that the solution is such that it doesn't really matter. If that is the case (i.e. this version is not any harder than the original one), I think you should just fix the I/O. But if this problem is harder, then by all means, keep it as it is but clarify the problem statement.

[Adrian Kuegel]

You are right, the problem statement like it is now is consistent with the original problem.
But also if one doesn't know the meaning, it doesn't clarify that you are wrong (therefore I did the mistake). I thought I should change it a bit to sound like: "For safety reasons, mines are not permitted to branch out; so within a mine there may not be any grid square with more than two directly connected grid squares. Note that therefore it is still allowed to have two mines running parallel."
Any idea how to improve the description is welcome
About the difficulty of the two problem variants: I think they are both equally difficult, you need backtracking to solve them (exponential in the number of diamonds at least, but with the given limits it is also possible to have it exponential in the length of the solution, if you use some pruning), and I didn't have to change much to get a program for the original problem.
I already send the corrected output to Carlos.

[Per]

Now I've solved the problem, and I still think it's a lot simpler this way (simpler to implement, that is -- I think both problems are NP-complete). My solution is less than 100 lines and contains almost no rules at all about how mines may be drawn. The only thing it cares about are the pairwise Manhattan distances of all the diamonds, and the diamonds' distance to the nearest '#'. I think if I were to fix it to solve the other version of the problem, it would become a lot longer.

[Adrian Kuegel]

You are right, it requires less lines of code to solve this problem. I needed about 200 lines for the other problem variant. But I don't think that more lines of code makes the problem more difficult, only more work.

[tiaral]

i still cannot understand the problem.

for this case:
6 3
###
#.#
#*#
#*#
#.#
###

why it has a solution?

and, what does "within a mine there may not be any grid square with more than two directly connected grid squares" mean?

[Adrian Kuegel]

Look at the 3rd example in the problem description; if there was not the restriction, that mines should not branch out, then the shortest length would be 12:

Code: Select all

###########
##.########
#....######
#--\...####
#..|.....##
##....|...#
###...\---#
###....|..#
###..|...##
####.|.####
###########

Note, that two neighbouring grid squares are not automatically connected, only if a mine goes through.
Therefore, a solution for your case would be:
###
#.#
#-#
#-#
#.#
###
I tried to indicate the direction of the mines, they are going east-west.

[tiaral]

thanks for your reply.
i have got AC by using backtracking. i wander how someone can solve it in 0ms?

[Destination Goa]

Per,

The only thing it cares about are the pairwise Manhattan distances of all the diamonds, and the diamonds' distance to the nearest '#'

Does your solution imply that there always exists manhattan-distance long path between any two diamonds? I.e. that "manhattan convex hull" of diamonds contains no '#'?

[Per]

Per,

The only thing it cares about are the pairwise Manhattan distances of all the diamonds, and the diamonds' distance to the nearest '#'

Does your solution imply that there always exists manhattan-distance long path between any two diamonds? I.e. that "manhattan convex hull" of diamonds contains no '#'?

No.

If all manhattan-distance paths between a pair of diamonds contain a "#", then it's easy to see that it would be better to dig two separate mines for these two diamonds than it would have been to connect them even if a manhattan-distance long path would have existed.

So some of the manhattan distance may not be the "actual" distances between diamonds, but these will not be used in an optimal solution anyway, so it doesn't matter.

[Destination Goa]

Per,

Yes, you are right. Thanks.