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