Problem link : contest practice Difficulty : EasyMedium Prerequisites : DP, Floodfill Problem : Determine, whether it's possible choose a cell in such a way that all the normal minions would not be trapped (will be free) after the antidote usage at that cell. Explanation : At first, let's find all the connected components of normal minions in the given matrix. Every connected component should should contain the maximal number of minions, that is, there should not be any possibility to extend each of the components with a normal minion. Then, if we take any component, all the minions from it will be either free or not. We can use a floodfill for the components search. For every component we can find the leftmost and the rightmost column and the topmost and the bottommost row. Having that found, it's easy to determine, whether the correspondent group of minions trapped or not. It it is not trapped, we don't have to do anything in order to rescue them, so we can just ignore this component. Let's see what happens else. Formally, we need to place a "cross" in the matrix, so we can consider a bounding rectangle of this area (i.e. a connected component of trapped minions). If the cross intersects the bounding rectangle then group will be free after placing the cross with the center in this cell. Otherwise, it will not, so the cell will not be applicable for us. Consider the bounding rectangle of some connected component. Let its bounding rectangle bottomleft and upperright coordinates be (X1, Y1) and (X2, Y2). The cross with the center at (X, Y) will not cross this rectangle if at least one of the following conditions will be held:
We can check all the above statements for all the rectangles at once via prefix sums on a rectangle, that is a pretty popular technique. We can have four prefixsums arrays for the different cases, that will make the solution easier. So, summing it all up again, we get the following solution:
This question is marked "community wiki".
asked 27 Apr '14, 14:00

I have one small comment about the solution, I think the solution does not handle the edge case where the line just touches the boundary of the rectangle (Which should also free the trapped minions) Example:
Here the current author code gives a output of "NO" however it should be possible to get all the trapped minions out. In the author solution, we can consider a bigger rectangle during flood fill to handle the above mentioned edge case:
You can find the updated author's solution here: https://www.codechef.com/viewsolution/15580376 answered 02 Oct '17, 00:42

How can prefix sums be used on a rectangle?