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;

}

## 0 Comments