# HackerEarth Rasta and Kheshtak problem solution

In this HackerEarth Rasta and Kheshtak problem solution, Rasta is a big fan of Kheshtaks. A Kheshtak is a rectangle that in each of it cells there is an integer.

Today rasta came up with an interesting problem, Biggest Common Subsquare (BCS). A Kheshtak is called a Square if the number of its columns is equal to the number of its rows. A Square S is called a subsqaue of a Kheshtak A if and only if we can turn A to S by deleting some of its rows and some of its columns (maybe none).

He gives you two Kheshtaks, A and B (A one is n × m and B is x × y).

## HackerEarth Rasta and Kheshtak problem solution.

`#include <bits/stdc++.h>#include <ext/pb_ds/assoc_container.hpp>#include <ext/pb_ds/tree_policy.hpp>using namespace __gnu_pbds;using namespace std;#define Foreach(i, c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)#define For(i,a,b) for(int (i)=(a);(i) < (b); ++(i))#define rof(i,a,b) for(int (i)=(a);(i) > (b); --(i))#define rep(i, c) for(auto &(i) : (c))#define x first#define y second#define pb push_back#define PB pop_back()#define iOS ios_base::sync_with_stdio(false)#define sqr(a) (((a) * (a)))#define all(a) a.begin() , a.end()#define error(x) cerr << #x << " = " << (x) <<endl#define Error(a,b) cerr<<"( "<<#a<<" , "<<#b<<" ) = ( "<<(a)<<" , "<<(b)<<" )\n";#define errop(a) cerr<<#a<<" = ( "<<((a).x)<<" , "<<((a).y)<<" )\n";#define coud(a,b) cout<<fixed << setprecision((b)) << (a)#define L(x) ((x)<<1)#define R(x) (((x)<<1)+1)#define double long doubletypedef long long ll;#define int lltypedef pair<int,int>pii;typedef vector<int> vi;typedef complex<double> point;template <typename T> using os =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;template <class T>  inline void smax(T &x,T y){ x = max((x), (y));}template <class T>  inline void smin(T &x,T y){ x = min((x), (y));}const int maxn = 710;int a[2][maxn][maxn];int n[2], m[2];int h[2][maxn][maxn], H[2][maxn][maxn];int p = 29 * 91, pw[maxn];int p2 = 701, pw2[maxn];inline void init(int x){    For(i,0,n[x]){        int cur = 0;        For(j,0,m[x]){            cur = (cur * 1LL * p);            cur = (cur + a[x][i][j]);            h[x][i][j] = cur;        }    }}inline int hashrow(int x,int row,int l,int r){    int ans = h[x][row][r];    if(l){        int X = (1LL * pw[r - l + 1] * h[x][row][l-1]);        ans = (ans - X);    }    return ans;}inline int hashcol(int x,int col,int l,int r){    int ans = H[x][col][r];    if(l){        int X = (1LL * pw2[r - l + 1] * H[x][col][l-1]);        ans = (ans - X);    }    return ans;}inline bool check(int s){    if(!s)  return true;    if(s > min(min(m[0], m[1]), min(n[0], n[1])))   return false;    memset(H, 0, sizeof H);    For(x,0,2)        For(j,0,m[x]){            int l = max(0LL, j - s + 1);            int cur = 0;            For(i, 0, n[x]){                int w = hashrow(x, i, l, j);                cur = (cur * 1LL * p2);                cur = (cur + w);                H[x][j][i] = cur;                //if(j)                //Error(cur, w);            }        }    vi mp;    For(x,0,2){        For(j,s-1,m[x])        For(i,s-1,n[x]){            int h = hashcol(x, j, i - s + 1, i);            //error(x);            //Error(i, j);            //error(H[x][j][i]);            //error(h);            if(!x)                mp.pb(h);            else{                int x = lower_bound(all(mp), h) - mp.begin();                if(x >= 0 && x < (int)mp.size() && mp[x] == h)                    return true;            }        }        if(!x){            sort(all(mp));            mp.resize(unique(all(mp)) - mp.begin());        }    }    return false;}int ans = 1e9;main(){    iOS;    pw[0] = pw2[0] = 1;    For(i,1,maxn)        pw[i] = (pw[i-1] * p), pw2[i] = (pw2[i-1] * p2);        For(x,0,2){            cin >> n[x] >> m[x];            For(i,0,n[x])                For(j,0,m[x])                {cin >> a[x][i][j]; a[x][i][j] += 16;}            init(x);        }        int l = 0, r = min(min(n[0], n[1]), min(m[0], m[1])) + 1;        while(r - l > 1){            int mid = (l+r)/2;            if(check(mid))                l = mid;            else                r = mid;        }        smin(ans, l);    cout << ans << endl;}`

### Second solution

`#include <bits/stdc++.h>using namespace std; long long s1[1<<10][1<<10],s2[1<<10][1<<10],ar1[1<<10][1<<10],ar2[1<<10][1<<10],pw1[1<<22],pw2[1<<22],n2,m2;long long l,r;long long n1,m1; long long get1(long a,long b,long c){       long long res=s1[a+c][b+c]-s1[a][b+c]-s1[a+c][b]+s1[a][b];    res*=pw1[2000000-a]*pw2[2000000-b];    return res;}long long get2(long a,long b,long c){    long long res=s2[a+c][b+c]-s2[a][b+c]-s2[a+c][b]+s2[a][b];    res*=pw1[2000000-a]*pw2[2000000-b];    return res;} vector<long long> have; bool solve(int X){    have.clear();    for (int i=0;i+X<=n1;i++)     for (int j=0;j+X<=m1;j++)      have.push_back(get1(i,j,X));        sort(have.begin(),have.end());    for (int i=0;i+X<=n2;i++)     for (int j=0;j+X<=m2;j++)        {            long long res=get2(i,j,X);            int id=lower_bound(have.begin(),have.end(),res)-have.begin();            if (id!=have.size()&&have[id]==res)             return true;        }    return false;} int main(){ios_base::sync_with_stdio(0);//cin.tie(0); pw1[0]=1;for (int i=1;i<=2000000;i++)     pw1[i]=pw1[i-1]*173; pw2[0]=1;for (int i=1;i<=2000000;i++)    pw2[i]=pw2[i-1]*137;  cin>>n1>>m1;for (int i=1;i<=n1;i++)    for (int j=1;j<=m1;j++)      cin>>ar1[i][j]; cin>>n2>>m2;for (int i=1;i<=n2;i++)    for (int j=1;j<=m2;j++)        cin>>ar2[i][j];for (int i=1;i<=n1;i++)    for (int j=1;j<=m1;j++)        s1[i][j]=s1[i][j-1]+s1[i-1][j]-s1[i-1][j-1]+ar1[i][j]*pw1[i]*pw2[j]; for (int i=1;i<=n2;i++)    for (int j=1;j<=m2;j++)        s2[i][j]=s2[i][j-1]+s2[i-1][j]-s2[i-1][j-1]+ar2[i][j]*pw1[i]*pw2[j]; l=0;r=700;while (l<r){    int mid=l+r+1;    mid/=2;    if (solve(mid))l=mid;        else    r=mid-1;}cout<<l<<endl;return 0;}`