RAHUL AND PUZZLE WORLD

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 referring the best online coding learning sites. 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-

  1. 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.
  2. First consider Dp, dp[i][j] indicates that the (i,j) position is the lower right corner, and the maximum square side length is, obviously dp[i][j] = min(dp[i-1][j ], dp[j][i-1], dp[i-1][j-1])+1.
  3. Then, after we made this decision, what would we do?
  4. 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.
  5. This can be done with binary search.
  6. 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";
    }
    }

Previous post CHOCOLATE DILEMMA
Next post FORM STRING

Leave a Reply

Your email address will not be published. Required fields are marked *