Last Updated on March 30, 2022 by Ria Pathak
CONCEPTS USED:
Dynamic programming
DIFFICULTY LEVEL:
Hard
PROBLEM STATEMENT(SIMPLIFIED):
For each query , give the size of maximum square with all pictures i.e. all ones from the given matrix of 1s and 0s.
For Example :
5 5
0 0 0 0 0
1 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0
5
4 4 5 4
3 3 3 4
3 1 3 3
2 3 3 4
2 1 5 4
For the 1st query, from (4,4) to (5,4) a square of size 1 is formed with all 1′s.
For the 2nd query, from (3,3) to (3,4) a square of size 1 is formed with all 1′s.
For the 3rd query, from (3,1) to (3,3) a square of size 1 is formed with all 1′s.
For the 4rth query, from (2,3) to (3,4) a square of size 2 is formed with all 1′s.
For the 5th query, from (2,1) to (5,4) a square of size 3 is formed with all 1′s.See original problem statement here
SOLVING APPROACH:
First lets calculate dp[i][j] — maximum square ending in cell ( i, j). For each cell if input matrix contain 0 then dp[i][j] = 0 else dp [i][j] = min( dp[i - 1][j - 1], dp[i−1][j], dp[i][j−1]) + 1.
We will use binary search to find the answer. Lets fix some value x. For each square ( i, j)..( i + x - 1, j + x - 1) we need to find maximum and compare it to x. To find maximum we can use 2D sparse table.
In simple words-
- Give you a 0-1 matrix, then Q queries, each time you query a rectangular area, the maximum length of a square is the largest one.
- First consider Dp,
dp[i][j]indicates that the(i,j)position is the lower right corner, and the maximum square side length is, obviouslydp[i][j]=min(dp[i-1][j ], dp[j][i-1], dp[i-1][j-1])+1.- Then, after we made this decision, what would we do?
- Direct two-point answer, assuming that our two-point answer is mid, obviously the point in the upper left corner of this rectangular area is the waste point, and then query the maximum value of the remaining points, whether it is greater than or equal to m.
- This can be done with binary search.
- We will use binary search to find the answer. Let’s fix some value x. For each square ( i, j)..( i + x - 1, j + x - 1) we need to find the maximum and compare it to x. To find the maximum we can use a 2D sparse table.
SOLUTIONS:
#include <stdio.h>
#define N 1004
#define M 11
int max(int x,int y)
{
if(x>y)return x;
return y;
}
int min(int x,int y)
{
if(x<y)
return x;
return y;
}
int mx[N][N][M][M],dp[N][N],n,m,q,f[N][N],a,b,c,d;
int rmq(int a,int b,int c,int d)
{
int s1=0,s2=0;
while((c-a)>>s1)s1++;
while((d-b)>>s2)s2++;
s1--,s2--;
if(s1==-1)s1++;if(s2==-1)s2++;
return max(max(mx[a][b][s1][s2],mx[c-(1<<s1)+1][b][s1][s2]),max(mx[a][d-(1<<s2)+1][s1][s2],mx[c-(1<<s1)+1][d-(1<<s2)+1][s1][s2]));
}
int main()
{
scanf("%d%d",&n,&m);
//in>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&f[i][j]);
//in>>f[i][j];
if(f[i][j])dp[i][j]=min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
mx[i][j][0][0]=dp[i][j];
for(int k=0;k<=10;k++)
for(int l=0;l<=10;l++)
for(int i=1;i+(1<<k)-1<=n;i++)
for(int j=1;j+(1<<l)-1<=m;j++)
if(k)
mx[i][j][k][l]=max(mx[i][j][k-1][l],mx[i+(1<<(k-1))][j][k-1][l]);
else if(l)
mx[i][j][k][l]=max(mx[i][j][k][l-1],mx[i][j+(1<<(l-1))][k][l-1]);
scanf("%d",&q);
//in>>q;
while(q--)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
//in>>a>>b>>c>>d;
int lb=1,rb=min(c-a,d-b)+1,ans=0;
while(lb<=rb)
{
int mid=(lb+rb)>>1;
if(rmq(a+mid-1,b+mid-1,c,d)>=mid)ans=mid,lb=mid+1;
else rb=mid-1;
}
printf("%d\n",ans);
//out<<ans<<"\n";
}
}
#include<bits/stdc++.h>
#include<cstring>
#include<algorithm>
#include <iosfwd>
using namespace std;
#define N 1004
#define M 11
int mx[N][N][M][M],dp[N][N],n,m,q,f[N][N],a,b,c,d;
int rmq(int a,int b,int c,int d)
{
int s1=0,s2=0;
while((c-a)>>s1)s1++;
while((d-b)>>s2)s2++;
s1--,s2--;
if(s1==-1)s1++;if(s2==-1)s2++;
return max(max(mx[a][b][s1][s2],mx[c-(1<<s1)+1][b][s1][s2]),max(mx[a][d-(1<<s2)+1][s1][s2],mx[c-(1<<s1)+1][d-(1<<s2)+1][s1][s2]));
}
int main()
{
/*ifstream in;
ofstream out;
in.open(R"(D:\PrepByte\Coding Platform\Dynamic Programming\29-02-2020\RAHPZ\tc\RAHPZ_12.in)");
out.open(R"(D:\PrepByte\Coding Platform\Dynamic Programming\29-02-2020\RAHPZ\tc\RAHPZ_12.out)");*/
scanf("%d%d",&n,&m);
//in>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&f[i][j]);
//in>>f[i][j];
if(f[i][j])dp[i][j]=min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
mx[i][j][0][0]=dp[i][j];
for(int k=0;k<=10;k++)
for(int l=0;l<=10;l++)
for(int i=1;i+(1<<k)-1<=n;i++)
for(int j=1;j+(1<<l)-1<=m;j++)
if(k)
mx[i][j][k][l]=max(mx[i][j][k-1][l],mx[i+(1<<(k-1))][j][k-1][l]);
else if(l)
mx[i][j][k][l]=max(mx[i][j][k][l-1],mx[i][j+(1<<(l-1))][k][l-1]);
scanf("%d",&q);
//in>>q;
while(q--)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
//in>>a>>b>>c>>d;
int lb=1,rb=min(c-a,d-b)+1,ans=0;
while(lb<=rb)
{
int mid=(lb+rb)>>1;
if(rmq(a+mid-1,b+mid-1,c,d)>=mid)ans=mid,lb=mid+1;
else rb=mid-1;
}
printf("%d\n",ans);
//out<<ans<<"\n";
}
}
class Matrix
{
// method for Maximum size square sub-matrix with all 1s
static void printMaxSubSquare(int M[][])
{
int i,j;
int R = M.length; //no of rows in M[][]
int C = M[0].length; //no of columns in M[][]
int S[][] = new int[R][C];
int max_of_s, max_i, max_j;
/* Set first column of S[][]*/
for(i = 0; i < R; i++)
S[i][0] = M[i][0];
/* Set first row of S[][]*/
for(j = 0; j < C; j++)
S[0][j] = M[0][j];
/* Construct other entries of S[][]*/
for(i = 1; i < R; i++)
{
for(j = 1; j < C; j++)
{
if(M[i][j] == 1)
S[i][j] = Math.min(S[i][j-1],
Math.min(S[i-1][j], S[i-1][j-1])) + 1;
else
S[i][j] = 0;
}
}
/* Find the maximum entry, and indexes of maximum entry
in S[][] */
max_of_s = S[0][0]; max_i = 0; max_j = 0;
for(i = 0; i < R; i++)
{
for(j = 0; j < C; j++)
{
if(max_of_s < S[i][j])
{
max_of_s = S[i][j];
max_i = i;
max_j = j;
}
}
}
System.out.println("Maximum size sub-matrix is: ");
for(i = max_i; i > max_i - max_of_s; i--)
{
for(j = max_j; j > max_j - max_of_s; j--)
{
System.out.print(M[i][j] + " ");
}
System.out.println();
}
}
// Driver program
public static void main(String[] args)
{
int M[][] = {{0, 1, 1, 0, 1},
{1, 1, 0, 1, 0},
{0, 1, 1, 1, 0},
{1, 1, 1, 1, 0},
{1, 1, 1, 1, 1},
{0, 0, 0, 0, 0}};
printMaxSubSquare(M);
}
}
[forminator_quiz id="2186"]
This article tried to discuss the concept of Dynamic programming. Hope this blog helps you understand and solve the problem. To practice more problems on Dynamic programming you can check out MYCODE | Competitive Programming.