CIRCLE - Editorial

editorial
, , , ,
1

Problem link : contest practice

Difficulty : Easy-Medium

Pre-requisites : DP, Flood-fill

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 flood-fill 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 bottom-left and upper-right 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:

  • X2 < X, Y2 < Y. That means that the figure lies completely in the upper-left quadrant relatively (X, Y).
  • X1 > X, Y2 < Y. That means that the figure lies completely in the upper-right quadrant relatively (X, Y).
  • X2 < X, Y1 > Y. That means that the figure lies completely in the bottom-left quadrant relatively (X, Y).
  • X1 > X, Y1 > Y. That means that the figure lies completely in the bottom-right quadrant relatively (X, Y).

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 prefix-sums arrays for the different cases, that will make the solution easier. So, summing it all up again, we get the following solution:

  • Using flood fill, find all the connected components of the trapped minions.
  • For each of the components find it’s bounding rectangle.
  • Mark the corners of the bounding rectangles in their respective rectangle prefix sums.
  • Iterate through all the cells of a matrix and check every cell with the usage of our previously built prefix sums. Each check can be performed in O(1) time, so we get overall complexity of O(N2).

Solutions: Setter Tester

2 Likes
2

How can prefix sums be used on a rectangle?

3

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:

1
7 5
BBBBB
BBWBB
BBBBB
BBBWB
BBBBB
BWBBB
BBBBB

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:

// top-left, bottom-right
ppi flood_fill(int i,int j){
    if(i < 0 or j < 0 or i >= n or j >= m or mp[i][j] == 'B' or vis[i][j]) return ppi(pii(inf,inf),pii(-inf,-inf));
    vis[i][j]=true;
    
    #ifdef AUTHOR_VERSION
      ppi ret=ppi(pii(i,j),pii(i,j));
    #else
      ppi ret=ppi(pii(i - 1,j - 1),pii(i + 1,j + 1));
    #endif
    
    ret=largest(ret,flood_fill(i+1,j));
    ret=largest(ret,flood_fill(i-1,j));
    ret=largest(ret,flood_fill(i,j+1));
    ret=largest(ret,flood_fill(i,j-1));

    return ret;
}

You can find the updated author’s solution here: https://www.codechef.com/viewsolution/15580376