In this **HackerEarth Coprimes problem solution,** John wants to cover his yard floor with mosaics. The yard floor is a n x m matrix and each cell is either a mosaic or a hole. John has invented the flipper machine. This machine has a size of k and can select a k x k square of the yard and flip the cells in it. By this action, every hole in the square becomes a mosaic and every mosaic in the square becomes a hole. It is illustrated by the following example:

The 2 x 2 square on the left has been flipped to the right one by the flipper with the size 2 and blacks are holes and whites are mosaics.

Help John to cover the floor of the yard completely by mosaics by using this machine. In each step, John selects a k x k square of the yard floor and sets the machine on it. He wants to compute the minimum steps needed to repair the yard floor.

## HackerEarth Mosaics and holes problem solution.

#include<bits/stdc++.h>
using namespace std;
const int M=1e3+10;
int ans,a[M][M],b[M][M],n,m,k;
void prt()//used for debug
{
cout<<"a: "<<endl;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cout<<a[i][j]<<" ";
cout<<endl;
}
cout<<"b: "<<endl;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cout<<b[i][j]<<" ";
cout<<endl;
}
cout<<endl;
}
int32_t main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
a[i][j]^=b[i][j];
b[i+1][j]^=b[i][j];
b[i][j+1]^=b[i][j];
b[i+1][j+1]^=b[i][j];
if(a[i][j]==0 && i+k-1<=n && j+k-1<=m)
{
ans++;
a[i][j]^=1;
b[i+1][j]^=1;
b[i][j+1]^=1;
b[i+1][j+1]^=1;
b[i+k][j]^=1;
b[i][j+k]^=1;
b[i+k][j+k]^=1;
}
else if(a[i][j]==0)
return cout<<-1<<endl,0;
//prt();
}
cout<<ans<<endl;
return 0;
}

### Second solution

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000 + 10;
bool b[maxn][maxn];
bool ps[maxn][maxn];
bool ar[maxn][maxn];
int main(){
int n, m, k;
cin >> n >> m >> k;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> b[i][j];
int ans = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++){
ps[i][j] = ps[i - 1][j - 1] ^ ps[i][j] ^ ps[i - 1][j] ^ ps[i][j - 1];
if(ps[i][j] == b[i][j]){
if(i + k > n + 1 || j + k > m + 1)
return cout << -1 << endl , 0;
ps[i][j] ^= 1;
ps[i + k][j] ^= 1;
ps[i][j + k] ^= 1;
ps[i + k][j + k] ^= 1;
ans++;
}
}
cout << ans << endl;
}

Thursday, January 13, 2022