MAXMEX - Editorial

Setter: Rezwan Arefin
Tester: Raja Vardhan Reddy
Editorialist: Taranpreet Singh

Simple

None

PROBLEM:

Given a sequence A of N integers, select the largest number of elements of A such that the MEX of the chosen sequence of selected elements is M, or determine that it’s impossible.

MEX of a sequence is the smallest positive integer not present in the sequence.

QUICK EXPLANATION

• If the MEX of A is already less than M, it is impossible to make the MEX of any subset of A exactly M, hence it’s impossible to select a subset of A with MEX M
• Otherwise, we can remove all occurrences of M in A. The remaining elements shall form the largest subset we can select which have MEX M.

EXPLANATION

We can view selecting a subset of A as the process of deleting the remaining elements. Let us assume the MEX of the sequence A is X.

Three cases arise

• X = M
The given array A already has MEX M, hence it is the largest subset which is the required answer.
• X < M
In this case, we actually need to add elements into A in order to make MEX equal to M. But, since we are not allowed to add new elements, it is impossible to make MEX M.
• X > M
In this case, we know that all elements in the range [1, X-1] appear at least once and M \in [1, X-1]. If we delete all occurrences of M from A, the MEX of A shall become M, since all elements in the range [1, M-1] are still present, but M is not. Hence, in this case, the required subset size is N less the frequency of M in A.

Bonus
Given a sequence A with N elements, find the minimum number of operations to make MEX exactly M if the following operations are allowed.

• Remove an element
• Change the value of an element

TIME COMPLEXITY

The time complexity is O(N) or O(N*log(N)) per test case, depending upon implementation.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int N = 1e5 + 5;
int t, n, m, a[N];

int main() {
scanf("%d", &t);
while(t--) {
scanf("%d %d", &n, &m);

set<int> st;
int ans = 0, x;
for(int i = 0; i < n; ++i) {
scanf("%d", &x);
if(x != m) st.insert(x), ++ans;
}

int mex = 1;
while(st.count(mex)) ++mex;

if(mex != m) ans = -1;
printf("%d\n", ans);
}
return 0;
}

Tester's Solution
//raja1999

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

//std::ios::sync_with_stdio(false);
int a[100005],cnt[100005];
main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
int n,m,i;
cin>>n>>m;
rep(i,n){
cin>>a[i];
if(a[i]<=m){
cnt[a[i]]+=1;
}
}
f(i,1,m){
if(cnt[i]==0){
break;
}
}
if(i!=m){
// not possible to choose
cout<<-1<<endl;
}
else{
// n-occ(m) elements
cout<<n-cnt[m]<<endl;
}

// clearing cnt
rep(i,n){
if(a[i]<=m){
cnt[a[i]]--;
}
}
}
return 0;
}

Editorialist's Solution
import java.util.*;
import java.io.*;
class MAXMEX{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni(), M = ni();
int mex = 1;
TreeSet<Integer> set = new TreeSet<>();
int cnt = 0;
for(int i = 0; i< N; i++){
int x = ni();
if(x == M)continue;
cnt++;
while(set.contains(mex))mex++;
}
if(mex == M)pn(cnt);
else pn(-1);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
void run() throws Exception{
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new MAXMEX().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}

StringTokenizer st;
}

}

String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
}catch (IOException  e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}

String nextLine() throws Exception{
String str = "";
try{
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}


Feel free to share your approach. Suggestions are welcomed as always.

4 Likes

What if given set is [1,2,4,5,6,8,9] and given M=7 , then largest subset can be [4,5,6,8,9]?

12 Likes

https://www.codechef.com/viewsolution/34620457
Can someone please explain Why i got an WA?

No, in that case 1 will be the MEX value

1 Like

i made the same (incorrect) assumption
the smallest positive number was asked , which in your provided set is 1 (not 7)

2 Likes

No. The MEX is 1.

Answer is impossible, since there’s no subset with Mex > 3

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

Why did i get WA?

Can you see 1 in that subset? No, right? How is it 3?

no there wont be any valid subset because the mex of the set is already smaller than that required

MEX of a sequence is the smallest positive integer not present in the sequence.

MEX, i.e. the smallest positive integer which does not occur among the chosen elements.

@taran_1407 there is lot of difference between these two statement.

MEX, i.e. the smallest positive integer which does not occur among the chosen elements. : it means you are talking about the chosen elements only

13 Likes

please tell me why I have got WA ,i have used the approach that the largest number of possible elements in an optimal subset should be all the bigger ones the M and if all the elements smaller than M i.e [1,M-1] exist then ad that to count
my_solution

statement was very confusing… it should have been clearly said that there can be repeating elements

5 Likes

https://www.codechef.com/viewsolution/34614882
Can someone please check why am I getting WA, I think I got the approach right and I checked on custom cases too. Someone pls review.

Point 1 of Quick Explanation
Let, M=8
{1,3,4,5,6,7,9,10}
MEX of given set is 2 which is less than M, so ans should be -1.

But a possible subset {4,5,6,7,9,10} gives MEX=8.

1 Like

messed up cause I didn’t consider multiple occurences.

3 Likes

it shall give mex as 1

1 Like

agree with that

I don’t think the set you mentioned latter has mex = 8. It is given in the question that we are to find the smallest positive number. It is not mentioned that it should belong to the given set.

1 Like

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

can someone help me what was wrong with my code??
pls review this code…