HackerEarth Rasta and Kheshtak problem solution YASH PAL, 31 July 2024 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;} coding problems solutions