Header Ad

HackerEarth Flip the World problem solution

In this HackerEarth Flip, the world problem-solution Flip the world is a game. In this game, a matrix of size N * M is given, which consists of numbers. Each number can be 1 or 0 only. The rows are numbered from 1 to N, and the columns are numbered from 1 to M.

The following steps can be called as a single move.

Select two integers x,y (1 <= x <= N and 1 <= y <= M) i.e. one square on the matrix.

All the integers in the rectangle denoted by (1,1) and (x,y) i.e. rectangle having top-left and bottom-right points as (1,1) and (x,y) are toggled(1 is made 0 and 0 is made 1).

For example, in this matrix (N = 4 and M = 3)

101

110

101

000

if we choose x = 3 and y = 2, the new state of matrix would be

011

000

011

000

For a given state of matrix, aim of the game is to reduce the matrix to a state where all numbers are 1. What is minimum number of moves required.


HackerEarth Flip the World problem solution


HackerEarth Flip the World problem solution.

#include <bits/stdc++.h>

using namespace std;

char arr [20 + 1][30 + 1];

int main()
{
int t , n , m , ans = 0;

cin >> t;

while(t--){

ans = 0;
cin >> n >> m;

for(int i = 0; i < n; i++){
for(int j = 0; j< m; j++){

cin >> arr[i][j];
}
}

for(int i = n - 1; i >= 0; i--){
for(int j = m - 1; j >= 0; j--){

if(arr[i][j] == '0'){
ans++;
for(int k = 0; k <= i; k++){
for(int h = 0; h <= j; h++){

if(arr[k][h] == '1') arr[k][h] = '0';
else arr[k][h] = '1';
}
}
}
}
}

cout << ans << "\n";
}

return 0;
}

Second solution

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<vector>
#include<cassert>
#include<sstream>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;
#define pb push_back
#define mp make_pair
#define clr(x) x.clear()
#define sz(x) ((int)(x).size())
#define F first
#define S second
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,b) for(i=0;i<b;i++)
#define rep1(i,b) for(i=1;i<=b;i++)
#define pdn(n) printf("%d\n",n)
#define sl(n) scanf("%lld",&n)
#define sd(n) scanf("%d",&n)
#define pn printf("\n")
typedef pair<int,int> PII;
typedef vector<PII> VPII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long LL;
#define MOD 1000000007
LL mpow(LL a, LL n)
{LL ret=1;LL b=a;while(n) {if(n&1)
ret=(ret*b)%MOD;b=(b*b)%MOD;n>>=1;}
return (LL)ret;}
int main()
{
int t;
sd(t);
while(t--)
{
int n,m,i,j,a[60][60]={};
vector <string> board;
sd(n),sd(m);
board.resize(n);
for(i=0; i<n; i++)
cin >> board[i];
for(i=n-1;i>=0;--i)
for(j=m-1;j>=0;--j)
{
if(i==n-1&&j==m-1)
a[i][j]=0;
else if(i==n-1)
a[i][j]=a[i][j+1];
else if(j==m-1)
a[i][j]=a[i+1][j];
else
a[i][j]=a[i+1][j]+a[i][j+1]-a[i+1][j+1];
if((a[i][j]%2==1&&board[i][j]=='1')||(a[i][j]%2==0&&board[i][j]=='0'))
a[i][j]++;
}
pdn(a[0][0]);
}
return 0;
}

Post a Comment

0 Comments