Can someone share their approach to solve the last problem from Innerve’s Summer Code Challenge .
Problem link - www.codechef.com/ISCC2017/problems/RUINEDF
2 Likes
First lets simplify the problem a little bit. Lets say that the floor is divided into N \times N squares. Now with one sweep you can remove either a complete row or a complete column.
You can convert this problem into a bipartite graph. Each row and each column gets converted into a vertex and for each * you create an edge that connects the corresponding row vertex with the corresponding column vertex. Now you have a known graph problem. You want to choose a minimal subset of vertices, so that at least one of the end vertices of each edge is in that subset. It’s called a “vertex cover”. Since the graph is bipartite (row vertices / column vertices), you can apply Kőnig’s theorem, and look for a maximum matching instead. You can use Hopcroft-Karp to accomplish this task in O(|E| \sqrt{|V|}) time.
Now to the harder task, where the floor is divided into (N + 1) \times N squares.
You can simply distinguish between two cases. Either the last row gets sweeped by the robot, then the answer is the maximal matching of the first N rows plus 1. Or you need to make vertical sweeps for each * in the last row. So you can apply these sweeps first, then the last row is free from $*$s and you can again compute the maximal matching of the first N rows. The answer to the problem will be the minimum of both cases. So the time complexity will be O(N^2\sqrt{N}).
Here is my implementation: 14636846 Sorry for the huge amount of commented lines. I first tried to solve the maximum matching part with Edmond-Karp (since you can model it as a maximum flow problem), but that approach turned out to slow (O(n^4) I think). But you should be fine if you just look at the main function and ignore all comments.
3 Likes