MEXPROB - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Soumyadeep Pal
Tester: Utkarsh Gupta
Editorialist: Taranpreet Singh

DIFFICULTY

Easy-Medium

PREREQUISITES

Binary Search, Two pointers.

PROBLEM

The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:

  • The MEX of [2, 2, 1] is 0 because 0 does not belong to the array.
  • The MEX of [3, 1, 0, 1] is 2, because 0 and 1 belong to the array, but 2 does not.
  • The MEX of [0, 3, 1, 2] is 4, because 0, 1, 2 and 3 belong to the array, but 4 does not.

You are given an array A of length N. You create a list B consisting of the MEX-es of all subarrays of the array A. Formally, for all pairs (l, r) such that 1 \leq l \leq r \leq N, you calculate MEX(A_l, A_{l + 1}, \dots, A_r) and append the value in the list B. Find the K-th smallest value in the list B.

QUICK EXPLANATION

  • Binary search on the final answer, now you need to count the number of subarrays of A having MEX at least x
  • For a chosen MEX M, For each left end 0 \leq l \lt N, find the smallest right end r such that subarray A_{l,r} contains all integers in range [0, M-1]. Sum of N-r for each left end is the number of subarrays.
  • When moving the left end one step to the right, only one element A_l is removed. If A_l \lt M and Number of occurrences of A_l in the range [l+1, r] is 1, the right end r needs to move till next occurrence of A_l is found.

EXPLANATION

The brute force solution here would be to consider all subarrays and compute their MEX and add them to a list and sort it. We can simply find K-th smallest element. This is sufficient for 10 points.

The reason this approach cannot be extended for the full solution is that there are N^2 subarrays, and if we consider them one by one, the time complexity cannot be better than O(N^2) which is not acceptable.

The MEX of any subarray can be in the range [0, N] only, so the final answer has to be in the range [0, N].

Idea attempt 1

But it is tricky to count the number of subarrays having MEX equal to a specific value. One tempting idea would be to try to count the number of subarrays having MEX M. We need to count the number of subarrays which contain all integers in the range [0, M-1], but not M.

One way to do that is for a fix M, divide the array A at each occurrence of M. For each part, now we only need to count the number of subarrays containing all elements in the range [0, M-1]. This can be done, if we maintain a right end pointer and move the left end one step at a time. For each left end, we keep extending the right end, until there is at least one occurrence of each element in the range [0, M-1].

Refining idea 1

While the above approach works, it requires O(N) work to count the number of subarrays for each MEX. There are N+1 candidates for MEX, so this would take O(N^2) time to compute the number of subarrays having each MEX which is not fast enough.

The problem was that we had to divide the array by occurrences of M. Let’s allow occurrences of M as well. Now, the mex of subarray would be \geq M.

Idea 2

Given a mex M, find the number of subarrays having MEX \geq M. This only requires us to count every subarray, which contains all elements in the range [0, M-1]. Let’s call this subarray good.

We can see that if subarray A_{l, r} is good, then subarray A_{l, r+1} is good as well. If subarray A_{l, r} is not good, then subarray A_{l, r-1} is not good.

Hence, for each left end l, there’s a unique right end r such that all subarrays A_{l, r'} with r \leq r' \lt N are good. We just need to find this right end r. There would be exactly N-r subarrays with that left end which are good. If no such r exist, then assume r = N.

How to find right ends for each left end?

Let’s start by finding right end for l = 0. Let’s say we have found the right end. How does the right end changes if we move left end from l = 0 to l = 1?

Only element A_l is removed. If A_l \geq M or there’s another occurrence of A_l in subarray A_{l+1, r}, then subarray A_{l+1, r} is good. Otherwise, we need to move the right end toward the right, till we either reach the end of the array, or we find an occurrence of A_l.

We can maintain a count array storing the number of occurrences of each element in the current subarray.

Since the right end moves only towards the right and can move at most N steps, the whole process takes O(N) time.

Returning to the original problem

Now we know how to count the number of subarrays with MEX \geq M. We need to find K-th smallest MEX. Our original problem is equivalent to finding K' = (N*(N+1))/2-K+1-th largest MEX.

Now, we can binary search on the MEX, if the number of subarrays with MEX \geq M is \geq K', then the final answer is \geq M, otherwise, the final answer is \lt M.

TIME COMPLEXITY

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

SOLUTIONS

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

#define int long long
const int N = 100001;
int n, k, a[N], cnt[N];


int fun(int x) {
  for (int i = 0; i <= n; i++) {
    cnt[i] = 0;
  }
  int mex = 0, r = 0;
  while (r < n && mex < x) {
    cnt[a[r]]++;
    r++;
    while (cnt[mex]) mex++;
  }
  if (mex < x) return 0;
  int ans = (n - r + 1);
  for (int l = 1; l < n; l++) {
    --cnt[a[l - 1]];
    if (a[l - 1] < x && cnt[a[l - 1]] == 0) {
      while (r < n && cnt[a[l - 1]] == 0) {
        cnt[a[r]]++;
        r++;
      }
    }
    if (a[l - 1] < x && cnt[a[l - 1]] == 0) break;
    ans += (n - r + 1);
  }
  return ans;
}

void solve() {
  cin >> n >> k;
  for (int i = 0; i < n; i++) cin >> a[i];
  int l = 1, r = n, ans = 0;
  int mx = n * (n + 1) / 2;
  while (l <= r) {
    int mid = (r + l) / 2;
    if (fun(mid) >= (mx - k + 1)) {
      ans = mid;
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  cout << ans << '\n';
}

signed main(){
  int t; cin >> t;
  while (t--) solve();
  return 0;
}
Tester's Solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#include <chrono>
#include <random>
#define ll long long int
#define ull unsigned long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
#define loop(i,a,b) for(ll i=a;i<=b;i++)
#define vi vector <int>
#define vs vector <string>
#define vc vector <char>
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define deb(x) cerr<<#x<<' '<<'='<<' '<<x<<'\n'
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(val)  no. of elements strictly less than val
// s.find_by_order(i)  itertor to ith element (0 indexed)
typedef vector<vector<ll>> matrix;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
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) {
            assert(cnt > 0);
            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, ' ');
}
void solve()
{
    ll n=readInt(1,100000,' ');
    ll total=(n*(n+1))/2;
    ll k=readInt(1,total,'\n');
    ll arr[n+1]={0};
    for(int i=1;i<=n;i++)
    {
        if(i!=n)
            arr[i]=readInt(0,n,' ');
        else
            arr[i]=readInt(0,n,'\n');
    }
    k=total+1-k;
    int l=0,r=n+1;
    while(l<=r)
    {
        int mid=(l+r)/2;
        // Number of subarrays with mex atleast mid
        int cnt[n+1]={0};  // Correct it
        int i=1;
        int j=0;
        int taken=0;
        ll good=0;
        while(true)
        {
            if(taken<mid)
            {
                j++;
                if(j>n)
                    break;
                cnt[arr[j]]++;
                if(cnt[arr[j]]==1 && arr[j]<mid)
                    taken++;
            }
            else
            {
                good+=(n+1-j);
                cnt[arr[i]]--;
                if(cnt[arr[i]]==0 && arr[i]<mid)
                    taken--;
                i++;
                if(i>n)
                    break;
            }
        }
        if(good>=k)
            l=mid+1;
        else
            r=mid-1;
    }
    cout<<r<<'\n';
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T=readInt(1,30000,'\n');
    //cin>>T;
    int t=0;
    while(t++<T)
    {
        //cout<<"Case #"<<t<<":"<<' ';
        solve();
        //cout<<'\n';
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class MEXPROB{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni();
        long K = (N*(long)(N+1))/2 - nl()+1;
        int[] A = new int[N];
        for(int i = 0; i< N; i++)A[i] = ni();
        
        int lo = 0, hi = N;
        while(lo < hi){
            int mid = lo + (hi-lo+1)/2;
            long count = countSubarrays(A, mid);
            if(count >= K)lo = mid;
            else hi = mid-1;
        }
        pn(lo);
    }
    //Returns number of subarrays having mex >= x
    long countSubarrays(int[] A, long x){
        int N = A.length;
        if(x == 0)
            return (N*(long)(N+1))/2;
        
        int[] cnt = new int[1+N];
        int mex = 0, r = 0;
        while(r < N && mex< x){
            cnt[A[r]]++;
            while(mex < x && cnt[mex] > 0)mex++;
            r++;
        }
        if(mex < x)return 0;
        long count = N-r+1;
        for(int l = 0; l < N-1; l++){
            cnt[A[l]]--;
            while(r < N && A[l] < x && cnt[A[l]] == 0){
                cnt[A[r]]++;
                r++;
            }
            if(r == N && A[l] < x && cnt[A[l]] == 0)break;
            count += N-r+1;
        }
        return count;
    }
    //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 MEXPROB().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:

2 Likes

There are no full AC submissions in Python 3
Even talking about 10 points
0 users in Div 3
4 users in Div 2
1 user in Div 1

Is it that no one could solve this problem during the contest or is it really unsolvable using Python?
If possible could someons give a complete accepted Python code.

2 Likes

in java even after using fast input-output brute force approach for 10 points is also not scorable
https://www.codechef.com/viewsolution/52290114
here is the code if there is some error pls tell

1 Like

I do not know why segment trees failed for this.

  1. Binary search on the actual answer.
    2)For a given mex M, find out how many subarrays are there whose mex<=M. If that count>=K, then M can be a possible answer.
  2. To count the number of subarrays whose mex<=M, for each r from 0 to n-1 , try to find minimum left index such that mex from r to l is <=M. The mexes from r to l follow an increasing sequence. So I tried to binary search l for each r.
  3. In order to find out mex from r to l, I used the first technique as outlined here. (c++ - Please tell me the efficient algorithm of Range Mex Query - Stack Overflow).

That way the complexity came to N(logN)^2 kind of. Still I am getting TLE. Anyone can point out the fallacy?

P.S The entire time I tried solving this problem, I thought how @taran_1407 would approach this problem.

Also in the Olympic problem, I can hardly see any python accepted code.

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

2 Likes

Your code takes n^3 time

N (logn)^2 solution was not intended for full score.

Oho…Okayyyy…

pls can you tell any more efficient method to find all subarrays
i took this approach mentioned in this article

1 Like

Hi, that’s what the editorial is all about.

Hey, here is the link to my TLE code for this problem. I don’t know why it is not getting 10 pts.
https://www.codechef.com/viewsolution/52289211

i tried the brute force approach but i couldn’t get 10points, may i know the criteria for getting 10points? like whats the max time complexity?

N^2

1 Like

Solution: 52034050 | CodeChef could you tell where i was exceeding n^2 complexity? (in calculating mexes?)

Sorting takes N^2.logn time

1 Like

Ya, time limits for this problem were very very strict.

anyone who did the Subtask(30 points), what was the approach and Time complexity?

Solution: 52256389 | CodeChef… Help!!

I am encountering this MEX for the first time. Please can anyone tell me what is MEX of array a=[2]?
I am trying the brute force method first but I don’t know how to calculate the MEX of an array.