PROBLEM LINKS
DIFFICULTY
CHALLENGE
EXPLANATION
This problem is not NP-hard almost for sure, but still for sure it is hard! Even though the input given is just two numbers up to 100 each, no one found the optimal solution for all cases (or maybe only Tomasz did :)). Let’s see what we can do with this problem.
Consider cells with ‘#’ characters as vertices of a graph, and pairs of neighbouring cells as edges of the same graph. You can understand from the problem statement that this graph should be a tree. A simple and well-known fact is that for any tree V = E+1, where V is the number of its vertices and E is the number of its edges. Suppose we put ‘#’ in every cell of the grid. In this case we have V = N * M and E = (N-1) * M + N * (M-1) (it’s easy to see why this is so). Now let’s remove K cells and put ‘.’ in them. Then we’ll have V = N * M - K and E = (N-1) * M + N * (M-1) - 4 * K + B + 2C + P, where B is the number of ‘.’ cells on the border of the grid, C is the number of ‘.’ cells at the corners, and P is the number of pairs of neighbouring ‘.’ cells – generally, each removed cell removes 4 edges, but sometimes there are unexisting and twice-removed edges among those. From V = E+1 we can get a formula for K: K = ((N-1) * (M-1) + B + 2C + P) / 3. If we say that Q = B + 2C + P, it can be easily seen that instead of minimizing K we may minimize Q. Also note that for all trees on the N * M grid the remainder of division of Q by 3 is the same (otherwise in some case we would get a non-integer K). Another thing to notice is that Q can’t be equal to 0, since in this case the border of the grid will form a cycle. So if we find a solution with Q equal to 1, 2 or 3, it will be optimal! The easiest case where the optimal solution can be found is when N is even and M equals 1 modulo 3 (or vice versa). The grid might look like this:
.#####################
##.#.#.#.#.#.#.#.#.#.#
#.###.#.###.#.###.#.##
##.#.###.#.###.#.###.#
#.###.#.###.#.###.#.##
##.#.###.#.###.#.###.#
#.###.#.###.#.###.#.##
##.#.###.#.###.#.###.#
#.#.#.#.#.#.#.#.#.#.##
#################### .#
Here we have B = 1, C = 1 and P = 0, so Q = 3. It can be easily seen how to build a similar grid for other N and M satisfying the conditions above.
This actually covers about 11/36 of all possible test cases, so there are still about 2/3 of the test cases left unsolved. The key is in searching for and optimizing different patterns for given N’ and M’, where X’ is the remainder of division of X by 6.
Another useful thing is hardcoding the answers for the cases when one of the dimensions is small using dynamic programming, but this is quite difficult.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.