CENS20B - Editorial

PROBLEM LINK:

Practice
Contest

Setter & Editorialist: Aman Dwivedi
Tester: Jatin Nagpal

DIFFICULTY:

Medium

PREREQUISITES:

Dynamic Programming, Binary Search, 2D Sparse Table

PROBLEM:

You need to answer Q queries on the matrix:

  • Each query is provided with coordinates that form a rectangle.
  • The answer to the query is the size of the maximum square, which is located fully inside the query rectangle such that every row and every column is in non-decreasing order.

EXPLANATION:

Some initial thoughts

As the problem says that the row and column need to be in non-decreasing order of the square, so initially all the cells itself are the square of size 1. Now let’s find for each cell (i,j), the maximum size square that ends in this.

Suppose we are in some cell (i,j), we need to check whether the character in this cell is greater or equal to the character in (i-1,j) cell and (i,j-1) cell. Do we need to compare it with only these two cells?

Wait

See this case

\begin{bmatrix} z & b \\ a & c \end{bmatrix}

So now its quite obvious that we also need to compare with the diagonal cell too i.e (i-1,j-1).

Calculating DP

Now Lets calculate dp [ i ][j ] — maximum square ending in cell ( i , j ).

For each cell if the character in that cell is greater than or equal to its — left cell (dp[ i ][j-1 ]), up cell (dp[ i -1][j ]) and diagonal cell (dp[ i-1 ][j-1 ]), then:
dp[ i ][j ] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1 else,
dp[i][j] = 1

Wait is dp[ i ][j ] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1 always true ? No, when the minimum comes out to be 1, then you need to do some more camparson as when the minimum comes out to be 1, then the sqaures doesn’t overlap.

Example

See this case

\begin{bmatrix} a & b & c \\ c & d & f \\ g & a & i \end{bmatrix}

For the cell (3,3), the minimum comes out to be 1 but yet dp[i][j] = 1.

Answering Queries

The answer to each query can be find by using Binary Search. The minimum size square that can be formed is 1 while maximum size square that can be formed is min(x2-x1, y2-y1) + 1. Hence assign l = 1 while r = min(x2-x1, y2-y1) + 1.

Now we need to find the maximum size square and compare it with the middle. The maximum can be found by using the 2D-Sparse Table.

Time Complexity

Building Sparse Table takes O(NMlogNlogM) while answering a query take O(logN) time.

SOLUTIONS

Author’s Code
#include<bits/stdc++.h>
using namespace std;

const int MAX=1e3+5;
const int K=11;

int ma[K][K][MAX][MAX];
int lg[MAX];

void pre(){
  lg[0]=-1;
  for(int i=1;i<=1000;i++) lg[i]=lg[i>>1]+1;
}

int la(int x1,int x2,int y1,int y2){
  int x=lg[x2-x1+1];
  int y=lg[y2-y1+1];

  return max(max(ma[x][y][x1][y1],ma[x][y][x2-(1<<x)+1][y2-(1<<y)+1]),max(ma[x][y][x1][y2-(1<<y)+1],ma[x][y][x2-(1<<x)+1][y1]));
}

void solve(){
  int n,m,q; cin>>n>>m;
  string s[n];
  for(int i=0;i<n;i++) cin>>s[i];

  int dp[n][m];

  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      if(i==0 || j==0) dp[i][j]=1;
      else{
        if(s[i][j]>=s[i-1][j-1] && s[i][j]>=s[i-1][j] && s[i][j]>=s[i][j-1]){
          int temp=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]));
          if(temp==1){
            if(s[i-1][j]>=s[i-1][j-1] && s[i][j-1]>=s[i-1][j-1])
              dp[i][j]=2;
            else
              dp[i][j]=1;
          }
          else dp[i][j]=1+temp;
        }
        else dp[i][j]=1;
      }
    }
  }

  int lx=lg[n]+1;
  int ly=lg[m]+1;

  for(int x=0;x<lx;x++){
    for(int y=0;y<ly;y++){
      for(int i=0;i+(1<<x)<=n;i++){
        for(int j=0;j+(1<<y)<=m;j++){
          if(x==0 && y==0) ma[x][y][i][j]=dp[i][j];
          else if(x==0 && y!=0) ma[x][y][i][j]=max(ma[x][y-1][i][j],ma[x][y-1][i][j+(1<<(y-1))]);
          else if(x!=0 && y==0) ma[x][y][i][j]=max(ma[x-1][y][i][j],ma[x-1][y][i+(1<<(x-1))][j]);
          else ma[x][y][i][j]=max(max(ma[x-1][y][i][j],ma[x-1][y][i+(1<<(x-1))][j]),max(ma[x][y-1][i][j],ma[x][y-1][i][j+(1<<(y-1))]));
        }
      }
    }
  }

  cin>>q;

  while(q--){
    int x1,x2,y1,y2; cin>>x1>>y1>>x2>>y2;
    x1--; x2--;
    y1--; y2--;
    int l,r,ans=1;
    l=1;
    r=min(x2-x1,y2-y1)+1;

    while(l<=r){
      int mid=l+(r-l)/2;
      int temp=la(x1+mid-1,x2,y1+mid-1,y2);
      if(temp>=mid){
        ans=mid;
        l=mid+1;
      }
      else r=mid-1;
    }
    cout<<ans<<"\n";
  }
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  pre();
  solve();

return 0;
}
Tester's Code
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define MP make_pair
#define PB push_back
#define ll long long
// #define int long long
#define f(i,x,n) for(int i=x;i<n;i++)
#define ld long double
const int mod=1000000007;
// const int INF=1e18;
int n,m,a[1005][1005],q,dp[1005][1005];
string s[1005];
 
#define TP int
#define MAXN 2005
#define MAXM 2005
#define K 10
int lg[MAXN+1];
TP st[MAXN][K+1][MAXM][K+1];
TP func(TP a,TP b) {
	return max(a,b); //Just Edit this function
}
int init() {
	lg[1] = 0;
	for(int i=2; i<=MAXN; i++)
		lg[i] = lg[i/2] + 1;
	f(i,0,n)
		f(j,0,m)
			st[i][0][j][0]=dp[i][j];
	f(ir,0,n) {
		f(jc,1,lg[m]+1) {
			for(int ic=0;ic+(1ll<<(jc-1))<m;ic++) {
				st[ir][0][ic][jc]=func(st[ir][0][ic][jc-1],st[ir][0][ic+(1ll<<(jc-1))][jc-1]);				
			}
		}
	}
	f(jr,1,lg[n]+1) {
		f(ir,0,n) {
			f(jc,0,lg[m]+1) {
				f(ic,0,m) {
					st[ir][jr][ic][jc]=func(st[ir][jr-1][ic][jc],st[ir+(1ll<<(jr-1))][jr-1][ic][jc]);
				}
			}
		}
	}
	return 0;
}
int com(int x1, int y1, int x2, int y2)
{
	int kx=lg[x2-x1+1];
	int ky=lg[y2-y1+1];
	int arr[4];
	arr[0]=st[x1][kx][y1][ky];
	arr[1]=st[x1][kx][y2+1-(1ll<<ky)][ky];
	arr[2]=st[x2+1-(1ll<<kx)][kx][y1][ky];
	arr[3]=st[x2+1-(1ll<<kx)][kx][y2+1-(1ll<<ky)][ky];
	return func(func(arr[0],arr[1]),func(arr[2],arr[3]));
}
 
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m;
	f(i,0,n)
		cin>>s[i];
	f(i,1,n+1) {
		f(j,1,m+1) {
			a[i][j]=s[i-1][j-1]-'a';
			dp[i][j]=1;
			if(a[i][j]>=a[i-1][j] && a[i][j]>=a[i][j-1] && a[i][j]>=a[i-1][j-1] && a[i-1][j]>=a[i-1][j-1] && a[i][j-1]>=a[i-1][j-1])
				dp[i][j]=1+min({dp[i-1][j],dp[i-1][j-1],dp[i][j-1]});
		}
	}
	n++; m++;
	n+=30,m+=30;
	init();
	cin>>q;
	while(q--) {
		int x1,y1,x2,y2,ans=1;
		cin>>x1>>y1>>x2>>y2;
		int i=0,j=min(x2-x1,y2-y1);
		while(i<=j) {
			int mid=(i+j)/2;
			int val=com(x1+mid,y1+mid,x2,y2);
			if(val-(mid+1)>0) {
				ans=max(ans,mid+1);
				i=mid+1;
			}
			else {
				ans=max(ans,val);
				j=mid-1;
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}
7 Likes