EQUALMEX - Editorial

[notsoloud]

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3

Setter: Soumyadeep Pal
Tester: Tejas Pandey, Abhinav Sharma
Editorialist: Kanhaiya Mohan

DIFFICULTY:

Simple

PREREQUISITES:

MEX

PROBLEM:

You are given an array A containing 2\cdot N integers. Is it possible to reorder the elements of the array in such a way so that the MEX of the first N elements is equal to the MEX of last N elements?

QUICK EXPLANATION:

• Let i be the smallest number having less than 2 occurrences in A.
• The answer is YES if i has 0 occurrences.
• The answer is NO if i has 1 occurrence.

EXPLANATION:

Let us denote the subarray with first N elements as P and that with last N elements as Q.

We know that, for a particular number i to exist as the MEX of P as well as Q, all j (0 \leq j < i) must have atleast one occurence in P as well as atleast one occurence in Q. This means that there must be atleast two occurrences of j in the array A.

Let i be the smallest number such that, the number of occurence of i in A is less than 2.

• There are 0 occurrences of i in A: This means that the MEX of both P and Q is i.
• There is 1 occurrence of i in A: We can place this i either in P or in Q. If we place it in P, the MEX of Q becomes i. However, the MEX of P would atleast be (i+1). This means that the MEX of P and Q can never be equal.

Implementation: We store the count of each number in array A. Starting from 0, find the smallest number i having count less than 2. All numbers less than i can be distributed among P and Q such that there is atleast one occurrence in both. If i has count 0, the answer is YES. If it has count 1, the answer is NO.

TIME COMPLEXITY:

The time complexity is O(N) per test case.

SOLUTION:

Setter's Solution

#include<bits/stdc++.h>
using namespace std;

void solve() {
  int n;
  cin >> n;
  vector<int> f(n + 1);
  for (int i = 0; i < 2 * n; i++) {
    int x;
    cin >> x;
    f[x]++;
  }
  for (int i = 0; i <= n; i++) {
    if (f[i] == 0) break;
    if (f[i] < 2) {
      cout << "NO\n";
      return;
    }
  }
  cout << "YES\n";
}

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

Tester's Solution

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)

void solve()
{   
    int n;
    cin>>n;

    int freq[n+1] = {0};
    int x;

    rep(i, 2*n){
        cin>>x;
        freq[x]++;
    }

    int ok = 1;

    rep(i, n+1){
        if(freq[i]==0) break;
        else if(freq[i]==1){
            ok=0;
            break;
        }
    }

    cout<<(ok?"YeS":"nO")<<'\n';

}
 
signed main()
{

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r" , stdin);
    freopen("output.txt", "w" , stdout);
    #endif
    fast;
    
    int t = 1;
    cin>>t;
        
    for(int i=1;i<=t;i++)
    {    
       solve();
    }

}

Editorialist's Solution

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int t;
	cin>>t;
	while(t--){
	    int n;
	    cin>>n;
	    vector<int> a(2*n);
	    vector<int> cnt(n+1, 0);
	    for(int i = 0; i<2*n; i++){
	        cin>>a[i];
	        cnt[a[i]]++;
	    }
	    bool poss = true;
	    for(int i = 0; i<=n; i++){
	        if(cnt[i]==0){
	            break;
	        }
	        if(cnt[i]==1){
	            poss = false;
	            break;
	        }
	    }
	    if(poss){
	        cout<<"YES"<<endl;
	    }
	    else{
	        cout<<"NO"<<endl;
	    }
	}
	return 0;
}

[zephxr]

My Approach was to calculate MEX of the whole array. If frequency of every number less than MEX is greater than equal to 2, then answer is YES otherwise its NO.

Reason for calculating MEX of the whole array : If a number n has to be the MEX of the first part as well as second part of the array, that means, n should neither exist in first part nor in second part, which is one of the conditions of MEX.

My Solution - Click Here

[quantakg_6625]

My code passed all sample test cases, Please help me where i did wrong.
Thanks for your time. @zephxr @notsoloud

#include <bits/stdc++.h>
using namespace std;


int main() {
	int t=0;
	cin>>t;
	for(int e=0;e<t;e++)
	{
	    vector<int> a(100007,0);
	    int n,k,flag=1;
	    cin>>n;
	    for(int i=0;i<2*n;i++){
	        cin>>k;
	        a[k]++;
	    }
	    for(int i=0;i<=n;i++){
	       // cout<<a[i]<<" ";
	        if(a[i]==0)break;
	        
	        if(a[i]%2==1){
	            flag=0;
	            break;
	        }
	    }
	    if(flag)cout<<"YES\n";
	    else cout<<"NO\n";
	    
	}
    
    
}

[notsoloud]

@quantakg_6625

if(a[i]%2==1)

Suppose a[i] is 3. Here a[i] \%2 = 1, but you can place one occurrence of i in the first half, and other two in the second half. The answer would not be NO due to i.
Instead, you should change flag to 0 when a[i] = 1.

[zephxr]

Your AC solution - Click Here

Just changed your if condition
if(a[i]%2==0) to if(a[i]==1)

if any element appears only 1 time, then answer should be NO.

[voldemort_11]

If the occurrence is 1 then the ans is no…
But if the test case is 002223 here 3 is just occur 1 time then 022 023 both mex is 1. answer will be YES.

[ekatva]

@notsoloud

Let iii be the smallest number having less than 222 occurrences in AAA.

According to this, 1 will take place of i, not 3. And as there are 0 occourance of 1, answer will be printed “YES”.

[mayank_2807]

Nope ,First we check minimum number with zero occurrence if didnt found any number with zero occurrence then answer would be NO.

[chaitri19]

I am facing same issue. Here is my code:
#include
#include

using namespace std;
std::map<int,int> m;

int findmex(int n)
{
int i;
std::map<int,int>::iterator it;
for(i=0;i<2n;i++)
{
it=m.find(i);
if(it==m.end())
{
return i;
}
}
return 2n;
}

int main()
{
int t,i,j,n,x;
cin>>t;
int X[t];
for(i=0;i<t;i++)
{
cin>>n;
for(j=0;j<2*n;j++)
{
cin>>x;
std::map<int,int>::iterator it;
it=m.find(x);
if(it!=m.end())
{
m[x]=m[x]+1;
}
else
{
m[x]=1;
}
}
x=findmex(n);
int val=0,val1=0;
for (auto& x1:m) {
//cout<<“x1[]=”<<x1.first<<endl;
if(x<x1.first)
{
val=0;
}
else
{
val=1;
break;
}
}
//cout<<“val=”<<val<<endl;
if(val==0)
{
X[i]=1;
}
else
{
for (auto& x1:m) {
//cout<<“val1=”<<val1<<endl;
if(x<x1.first)
{
if(x1.second>=2)
{
val1=0;
}
else
{
val1=1;
break;
}
}
else
{
break;
}
}
if(val1==0)
{
std::map<int,int>::iterator it1;
it1=m.find(x-1);
if(it1!=m.end())
{
if(it1->second>=2)
{
X[i]=1;
}
else
{
X[i]=0;
}
}
else
{
X[i]=0;
}
}
else
{
X[i]=0;
}
}
m.clear();
}
for(i=0;i<t;i++)
{
if(X[i]==0)
{
cout<<“NO”<<endl;
}
else
{
cout<<“YES”<<endl;
}
}
return 0;
}

[ghostofuchiha]

why would having an element odd no of times(say number = y) and having all the elements before y from 0 to y-1 have non zero even no of occurrences … wrong answer??

[pyaari_billi]

Same approach

[iphone_11]

#include<bits/stdc++.h>
using namespace std;



int main(){
	
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		vector<int>v(2*n);
		int minn=0;
		map<int,int>mp;
		for(int i=0;i<2*n;i++){
			cin>>v[i];
			mp[v[i]]++;
			if(v[i]==minn){
				minn++;
			}
		}
		bool f=1;
		for(int i=0;i<minn;i++){
			if(mp[i]<2){
				cout<<"no"<<"\n";
				f=0;
				break;
			}
		}
		if(f){
			cout<<"yes"<<"\n";
		}
		
	}
}

My approach is to find the MEX of whole array and then check all the occurences of numbers before it have atleast two occurences then yes else NO
but iam facing WA someone help

[nishan_adm]

Hey, you are trying to find the MEX of the array, but since it is not guaranteed that the array would be sorted, the value of minn will not always be the MEX.

For example take the array 1 0 2 3, the MEX of this array should be 4, but according to your code, it will be 1.

Bonus point: Scanning and sorting the array before trying to calculate the MEX will solve the problem.

[iphone_11]

Yeah thank u so much