26 days ago

ANIRUDH • 0

Dehradun

Problem-2: Maximizing MEX

In this problem, we are given an integer array a of size n and a non-negative integer m, representing the number of allowed insert operations. We define the MEX (Minimum Excluded Value) of an array as the smallest non-negative integer that is not present in the array.

Our goal is to compute the maximum possible MEX that can be achieved by inserting at most m non-negative integers (possibly duplicates) into the array a.

Solution: Binary Search on Answer

This problem is efficiently solved using a binary search on the value of the MEX. Instead of trying to construct every possible outcome, we ask the question:
"Is it possible to achieve a MEX of at least X?"
This allows us to binary search the maximum valid MEX.

The logic is as follows:

1. Use a Set for Fast Lookup:
   Store all values of the array in an unordered set, allowing O(1) lookups to check if an integer is missing.

2. Define a Validity Function:
   For any candidate MEX x, count how many numbers in the range [0, x-1] are missing in the set. These are the numbers we would need to insert to make x a valid MEX.
   If the number of missing integers is ≤ m, then it is possible to make x the MEX.

3. Binary Search:
   Perform binary search in the range [0, n + m + 5] for the largest value x such that the validity function returns true.

4. Return the Maximum Valid MEX found.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll solution(int n, ll m, vector<int> a) {
    unordered_set<int> present(a.begin(), a.end());
    auto isValid = [&](ll x) {
        ll missing = 0;
        for (ll i = 0; i < x; ++i) {
            if (!present.count(i)) missing++;
        }
        return missing <= m;
    };

    ll low = 0, high = m + n + 5, ans = 0;
    while (low <= high) {
        ll mid = (low + high) / 2;
        if (isValid(mid)) {
            ans = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return ans;
}

int main() {
    int n;
    ll m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    cout << solution(n, m, a) << endl;
    return 0;
}

Complexity Analysis

Let X be the final maximum possible MEX value.

• Time Complexity: O(X)
  For each binary search iteration, we check all values from 0 to X. This results in O(X log X) in the worst case. However, due to small constraints on m and n, this is efficient.

• Space Complexity: O(n)
  An unordered set of size n is used to track the presence of integers in the original array.