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. 