MAXMEX - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

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

DIFFICULTY:

Simple

PREREQUISITES:

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.

  • Add an element
  • 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 comment(linker, "/stack:200000000")
//#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++;
	        set.add(x);
	        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;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    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());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

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

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

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

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 :frowning:
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.
Please clarify.

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…