Codeforces Round #356 (Div. 2) E / (Div. 1) C - Bear and Square Grid

Problem Statement:
Codeforces Round #356 (Div. 2) E / (Div. 1) C - Bear and Square Grid

Summary:
A \(N \times N\) grid where a cell is either empty or not, has the following properties: an empty cell is connected to its up, left, right, or bottom neighbour if its neighbour is also an empty cell. Compute the largest possible connected component in the grid, if we can perform one operation of transforming a \(k \times k\) square in the grid into empty cells.



Solution:
The solution employs a cool technique. The strategy is to check every possible placement of the \(k \times k\) square and record the maximum connected component obtained. The key is to make this strategy work in time.

Suppose that we have already computed all the connected components in the initial grid, such that we have the following informations:
- m[i][j] is the key of the connected component in which cell (i, j) belongs to.
- sz[key] is the size of the connected component 'key'.

The strategy is to perform a sliding window operation on each row of the grid. On each row, we form the \(k \times k\) square from the left side, and slide it one cell at a time to the right end of the row. We keep track of the number of non-empty cells that our current square covers, and also of all the connected components covered in the square.

When we slide our \(k \times k\) square to the right, say that our square currently covers column [L, L+k-1], what we do is we "peel off" the contributions from the column L of our square, and we add the contributions from column L+k, hence forming a new square [L+1, L+k] in O(k) time.

Also, for each position of the square, we check the upper, bottom, left and right cells that touches the border of our square for connected components. These connected components are now connected together because of our square and hence can be added to the total size of the connected component formed by our square. This check will also take O(k) per square.

Hence the total runtime complexity of this strategy is O(k*N*N).

Implementation:

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <deque>
#include <string>
using namespace std;

int n, k;
int a[510][510];
int m[510][510]; // map entry i j to key k
int vis[510][510];
int sz[510*510], vis_key[510*510];
int ans, cnt;
vector<int> backstack;
void ClearBackstack() {
  for (int i=0;i<backstack.size();++i){
    vis_key[backstack[i]]=0;
  }
  backstack.clear();
}
int ComputeSlice(int row, int j, vector<int>* bstack,
                 int* extra) {
  int sum =0;
  for(int i=row;i<row+k;++i){
    if (!a[i][j]) {
      sum += 1;
    } else {
      if (!vis_key[m[i][j]]) {
        *extra += sz[m[i][j]];
      }
      vis_key[m[i][j]]++;
      bstack->push_back(m[i][j]);
    }
  }
  return sum;
}
void ClearSlice(const vector<int>& bstack, int* extra) {
  for (int i = 0; i<bstack.size(); ++i) {
    vis_key[bstack[i]]--;
    if (!vis_key[bstack[i]]) {
      *extra -= sz[bstack[i]];
    }
  }
}
int CheckRow(int row, int col) {
  // [col ... col+k-1]
  if (row < 0 || row >= n) return 0;
  int sum=0;
  for (int j=col;j<col+k;++j){
    if(a[row][j] && !vis_key[m[row][j]]) {
      vis_key[m[row][j]]=1;
      backstack.push_back(m[row][j]);
      sum += sz[m[row][j]];
    }
  }
  return sum;
}
int CheckCol(int col, int row) {
  // [row ... row+k-1]
  if (col < 0 || col >= n) return 0;
  int sum=0;
  for (int i=row;i<row+k;++i){
    if(a[i][col] && !vis_key[m[i][col]]) {
      vis_key[m[i][col]]=1;
      backstack.push_back(m[i][col]);
      sum += sz[m[i][col]];
    }
  }
  return sum;
}
void dfs(int i, int j) {
  if (i<0 || j<0 || i>=n || j>=n) return;
  if (vis[i][j]) return;
  if (!a[i][j]) return;
  vis[i][j]=1;
  m[i][j]=cnt;
  sz[cnt]++;
  dfs(i-1,j);
  dfs(i+1,j);
  dfs(i,j-1);
  dfs(i,j+1);
}
void Solve() {
  for(int i=0;i<n;++i)for(int j=0;j<n;++j)m[i][j]=-1;
  ans = 0;
  cnt = 0;
  for(int i=0;i<n;++i){
    for(int j=0;j<n;++j){
      if (!a[i][j] || vis[i][j]) continue;
      sz[cnt]=0;
      dfs(i, j);
      cnt++;
    }
  }
  for (int row=0;row+k-1<n;++row){
    for (int i=0;i<cnt;++i) vis_key[i]=0;
    deque<int> window;
    deque<vector<int>> bstack;
    int sum = 0;
    int extra = 0;
    // prepare first window
    for(int j=0;j<k;++j){
      bstack.push_back({});
      window.push_back(ComputeSlice(row, j, &bstack.back(), &extra));
      sum += window.back();
    }
    int cur = 0;
    // compute, then slide
    for (int j=0;j+k-1<n;++j){
      cur = sum+extra;
      cur += CheckRow(row-1, j);
      cur += CheckRow(row+k, j);
      cur += CheckCol(j-1, row);
      cur += CheckCol(j+k, row);
      ans = max(ans, cur);
      ClearBackstack();
      if (j!=n-k) {
        sum -= window.front();
        window.pop_front();
        ClearSlice(bstack.front(), &extra);
        bstack.pop_front();
        bstack.push_back({});
        window.push_back(ComputeSlice(row, j+k, &bstack.back(), &extra));
        sum += window.back();
      }
    }
  }
  printf("%d\n",ans);
}

int main(){
  scanf("%d%d",&n,&k);
  string s;
  for(int i=0;i<n;++i){
    cin >> s;
    for (int j=0;j<n;++j){
      if(s[j]=='X') a[i][j]=0;
      else a[i][j]=1;
    }
  }
  Solve();
  return 0;
}