MINIL - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 2
Contest: Division 3

Author: Deepak Barnwal
Tester: Rahul Dugar
Editorialist: Aman Dwivedi

DIFFICLULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You are given a matrix with N rows and M columns, where each cell of matrix contains a character (.) or (*). Here (.) denotes water whereas (*) denotes a land. You task is calculate the minimum number of moves required to maximize the number of islands in a given matrix. In a single move, you can convert land to water and vice-versa.

An island is defined as the group of connected (*), such that is possible to move from one (*) to another (*) by moving vertically or horizontally to the adjacent cell.

QUICK EXPLANATION:

  • The number of islands will be more when the area of island will be minimum. The minimum area that island can have is 1.

  • The Maximum number of island in grid are \lceil \frac{N*M}{2} \rceil.

  • There are two types of arrangement possible when N*M is even.

  • There is only one arrangement possible when N*M is odd.

  • Finally, found out the minimum number of moves that are required in the any arrangement.

EXPLANATION:

Our primary goal is to maximize the number of islands in the grid. The number of islands will be more when the area of the island will be minimum, here the minimum area that island can have is 1. Now if there is a cell that contains land then all its adjacent cells should contain water.

Claim: Maximum number of island that a grid can have are \lceil \frac{N*M}{2} \rceil.

Proof

Let us assume that there is cell (i,j) which contains land, then all its adjacent cells should contain water. Let us classify the cells according to the parity.

If there is a cell (i,j), then the adjacent cells of this cell are (i-1,j), (i+1,j), (i,j-1) and (i,j+1). We can distinguish the cells and its adjacent cells on the basis of parity.

S=(i+j) \\ S_{up}=(i-1+j) \\ S_{down}=(i+1+j) \\ S_{left}=(i+j-1) \\ S_{right}=(i+j+1)

We can clearly see that the parity of S is different from that of S_{up}, S_{down}, S_{left} and S_{right}.

N*M is Odd

Here the number of even parity cells will be \lceil \frac{N*M}{2} \rceil, whereas odd parity cells will be \lfloor \frac{N*M}{2} \rfloor. We must fill land into even parity cells to maximize number of islands in a grid. Hence maximum number of islands in a grid are \lceil \frac{N*M}{2} \rceil.

N*M is Even

Here the number of even parity cells will be \frac{N*M}{2}, whereas odd parity cells will be \frac{N*M}{2}. We can fill land either into even parity cells or odd parity cells. Here maximum number of islands in a grid are \frac{N*M}{2}.

Hence the maximum number of island in a grid are \lceil \frac{N*M}{2} \rceil.

Since, we have maximized the number of islands in a grid. Now we are only left with performing minimum number of moves to achieve the maximum islands.

Case 1

N*M is Even.

In this case there are two types of arrangement possible:

  • Fill the land into even parity cells and water into odd parity cells.
  • Fill the land into odd parity cells and water into even parity cells.
Case 2

N*M is Odd.

In this case there is only one type of arrangement possible, as the even parity cells are more than that of odd parity cells:

  • Fill the land into even parity cells and water into odd parity cells.

Our secondary goal was to minimize the number of moves required. Hence we will pick the type of arrangement which requires less moves.

TIME COMPLEXITY:

O(N*M) per testcase.

SOLUTIONS:

Setter 
#include "bits/stdc++.h"
using namespace std;
#define int long long
signed main(){
    int Test = 1;
    cin>>Test;
    while(Test--){
        int n,i,m,j;
        cin>>n>>m;
        string s[n];
        for(i=0; i<n; i++)
            cin>>s[i];
 
        // .*.*
        int NOIL_1 = 0 , Changes_1 = 0;
        for(i=0; i<n; i++){
            for(j = 0; j<m; j++){
                if( ( i + j)%2 == 0  ){
                    if(s[i][j] != '.')
                        Changes_1++;
                }else{
                    NOIL_1++;
                    if(s[i][j] != '*')
                        Changes_1++;
                }
            }
        }
        
        // *.*.
        int NOIL_2 = 0 , Changes_2 = 0;
        for(i=0; i<n; i++){
            for(j = 0; j<m; j++){
                if( ( i + j)%2 == 0  ){
                    NOIL_2++;
                    if(s[i][j] != '*')
                        Changes_2++;
                }else{
                    if(s[i][j] != '.')
                        Changes_2++;
                }
            }
        }
 
        if(NOIL_1 > NOIL_2){
            cout<<Changes_1<<'\n';
        }else
        if(NOIL_2 > NOIL_1){
            cout<<Changes_2<<'\n';
        }else{
            cout<<min(Changes_1 , Changes_2)<<'\n';
        }
    }
    return 0;
}
Tester 
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int powm(int a, int b) {
	int res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
 
long long readInt(long long l, long long r, char endd) {
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true) {
		char g=getchar();
		if(g=='-') {
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g&&g<='9') {
			x*=10;
			x+=g-'0';
			if(cnt==0) {
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
 
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd) {
			if(is_neg) {
				x=-x;
			}
			assert(l<=x&&x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l, int r, char endd) {
	string ret="";
	int cnt=0;
	while(true) {
		char g=getchar();
		assert(g!=-1);
		if(g==endd) {
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt&&cnt<=r);
	return ret;
}
long long readIntSp(long long l, long long r) {
	return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
	return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
	return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
	return readString(l,r,' ');
}
 
 
 
string s[10];
void solve() {
	int n,m;
	cin>>n>>m;
	rep(i,0,n)
		cin>>s[i];
//	int n=readIntSp(1,10),m=readIntLn(1,10);
//	rep(i,0,n)
//		s[i]=readStringLn(m,m);
	rep(i,0,n)
		rep(j,0,m)
			assert(s[i][j]=='.'||s[i][j]=='*');
	int ans1=0,ans2=0;
	rep(i,0,n)
		rep(j,0,m) {
			ans1+=((i+j)&1)^(s[i][j]=='.');
			ans2+=((i+j)&1)^(s[i][j]=='*');
		}
	if((n&1)&&(m&1)) {
		cout<<ans1<<endl;
	} else
		cout<<min(ans1,ans2)<<endl;
}
 
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(10);
//	int t=readIntLn(1,1000);
	int t;
	cin>>t;
	fr(i,1,t)
		solve();
#ifdef rd
	cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}
Editorialist 
#include<bits/stdc++.h>
using namespace std;

void solve(){
  int n,m; cin>>n>>m;
  vector <string> s(n);

  int count_star[2]={},count_dot[2]={};

  for(int i=0;i<n;i++){
    cin>>s[i];
    for(int j=0;j<m;j++){
      if(s[i][j]=='*'){
        count_star[(i+j)%2]++;
      }
      else{
        count_dot[(i+j)%2]++;
      }
    }
  }

  if(n%2==0 || m%2==0){
    int total=(n*m)/2;
    int ans_1=abs(count_star[0]-total)+abs(count_dot[1]-total);
    int ans_2=abs(count_dot[0]-total)+abs(count_star[1]-total);

    cout<<min(ans_1,ans_2)<<"\n";
    return;
  }

  int star=(n*m)/2,dot=star;
  star++;
  int ans=abs(count_star[0]-star)+abs(count_dot[1]-dot);
  cout<<ans<<"\n";
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int t; cin>>t;
  while(t--){
    solve();
  }

return 0;
}

VIDEO EDITORIAL:

10 Likes
2

That’s thorough, I appreciate your editorials sir.

4 Likes
4

https://www.codechef.com/viewsolution/41893574

we can do it in two loops only but we have to use four counter
for each turn seperate counter for water and land.

void solve()
{
int n, m;
cin>>n>>m;
char c;
int first_l = 0,second_l = 0,first_w = 0, second_w = 0;
bool flag = true;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin>>c;
if(flag){
if(c == ‘.’){
first_w++;
}
else{
first_l++;
}
}
else{
if(c == ‘.’){
second_w++;
}
else{
second_l++;
}
}
flag = !(flag);
}
if(m%2 == 0)
flag = !(flag);
// cout<<flag<<endl;
}
// cout<<first_w<<first_l<<endl;
// cout<<second_w<<second_l<<endl;
if(n%2 != 0 and m % 2 != 0){
cout<<first_w + second_l<<endl;
}
else if(first_w + second_l > first_l + second_w)
cout<<first_l + second_w<<endl;
else
cout<<first_w + second_l<<endl;

}

5

WHATS WRONG IN THIS APPROACH : ANYONE ??

#include <bits/stdc++.h>
using namespace std;
int main() {
int t;std::cin >> t;
while(t–){
int n,m;std::cin >> n>>m;
char arr[n][m];char temp[n][m];

    for(int i=0;i<n;i++){
        string s;std::cin >> s;
        for(int j=0;j<m;j++){
            arr[i][j]=s[j];temp[i][j]=arr[i][j];
        }
    }
    int answer1=0;int answer2=0;
    for(int i=0;i<n;i=i+2){
        int x=i;int y=0;
        while(x<n&&y<m)
        {if(arr[x][y]=='*'){
            answer1++;
        }
        else{
            answer2++;
        }
            x++;y++;
        }
    }
    for(int i=2;i<m;i=i+2){
        int x=0;int y=i;
        while(x<n&&y<m)
        {if(arr[x][y]=='*'){
            answer1++;
        }
        else{
            answer2++;
        }
            x++;y++;
        }
    }
    
    for(int i=1;i<n;i=i+2){
        int x=i;int y=0;
        while(x<n&&y<m)
        {if(arr[x][y]=='*'){
            answer2++;
        }
        else{
            answer1++;
        }
            x++;y++;
        }
    }
    for(int i=1;i<m;i=i+2){
        int x=0;int y=i;
        while(x<n&&y<m)
        {if(arr[x][y]=='*'){
            answer2++;
        }
        else{
            answer1++;
        }
            x++;y++;
        }
    }
    
    long int jk=m*n;
    if(jk%2==0){
    if(answer1<answer2){
        std::cout << answer1 << std::endl;
    }
    else{
        std::cout << answer2 << std::endl;
    }}
    else{
        std::cout << answer1 << std::endl;
    }
}
return 0;

}

6

Can someone correct me for this test case
1
1 4
[ * * * * ]

according to me the answer should be 1 by just changing 2nd cell.
but the correct submission also accept others solution with answer 2 also.

1 Like
7

Where am I wrong?
#include<bits/stdc++.h>
#include
using namespace std ;
typedef long long ll;
typedef vector vi;
typedef vector vil;
typedef pair<int,int> pi;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define SORT(v) sort(v.begin(), v.end())
#define RSORT(v) sort(v.rbegin(),v.rend())
#define PRINT(x) cout<<x<<endl;
// #define ar array;

inline void solve() {
int t;cin>>t;
while(t–){
int m,n;cin>>n>>m;
int ans=0;
for(int i=0;i<n;i++){
string s="";
cin>>s;
if((nm)%2!=0){
for(int j=0;j<m;j++){
if((i+j)%2==0){
if(s[j]==’.’){
ans++;
}
}
else{
if(s[j]==’’){
ans++;
}
}
}
}
else{

        int c1=0,c2=0;
        for(int j=0;j<m;j++){
            if((i+j)%2==0){
                if(s[j]=='.'){
                    c1++;
                }
                else{
                    c2++;
                }
            }
            else{
                if(s[j]=='*'){
                    c1++;
                }
                else{
                    c2++;
                }
            }
            }
            ans+=min(c1,c2);
    }
    
}
PRINT(ans);

}
}

int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
}

8

n,m are greater than or equal to 2.

1 Like
11

Number of rows and columns is always greater than 1

1 Like
12

This isn’t a testcase for this problem, according to constrainsts n <= 2. This is why the accepted solutions give a different answer than what you would expect.

1 Like
13

okay got it Thanks

14

Don’t know why I’m getting WA, can anybody help?

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007 //1e9+7 ans%mod
#define ll long long
#define test_cases(x) int x; cin>>x; while(x–)
#define endl “\n”

void starter()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}

int main()
{
starter();
test_cases(t)
{
int n, m;
cin >> n >> m;
char s[n][m];
for (int i = 0; i < n; i++)
{
// string x;
// cin >> x;
for (int j = 0; j < m; j++)
{
char x;
cin >> x;
s[i][j] = x;
}
}

	int count = 0, count1 = 0;
	int flag = 1;
	//1->* -1->.
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (flag == 1)
			{
				if (s[i][j] == '.')
				{
					count++;
				}
				flag = -1;
			}
			else
			{
				if (s[i][j] == '*')
				{
					count++;
				}
				flag = 1;
			}
		}
		flag *= -1;
	}
	flag = -1;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (flag == 1)
			{
				if (s[i][j] == '.')
				{
					count1++;
				}
				flag = -1;
			}
			else
			{
				if (s[i][j] == '*')
				{
					count1++;
				}
				flag = 1;
			}
		}
		flag *= -1;
	}
	if ((n * m) % 2 == 1)	cout << count << endl;
	else cout << min(count, count1) << endl;
}
return 0;

}

15

Just comment down the statement,
flag = flag*(-1);
in both the nested for loops.
As this statement will give you wrong answer when n*m is not even.

16

Still getting WA :frowning:

17

I apologise if this is silly, but I’m not sure where my solution is going wrong: my solution
I took each row as a string vector, then I generated the two maximal island test cases using 2 strings.

I then compared both of them in a loop with the input to see which one of the two would require minimum swaps. (also considered only one test for the odd case: .… , ..…).

If someone could point out any flaws with the logic or the code, or any common edge cases that would trip this up, I would appreciate it.

18

copied question from leetcode–> number of islands

19

It’s a similar question. Don’t just assume it is copied. The Problem is good though.