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


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;
}