Speed up searching for the lowest element that is not in the array

Question

I try to solve this question: B. Informatics in MAC at Codeforces To solve it, I think I need to calculate the prefix and suffix array of MEX. I made observation that making only 1 subsegment will give good answer. We are required to make at least 2, but we know that MEX of every segment must be equal, so making segments as large as possible is optimal.

Due to this, we just can calculate prefix and suffix arrays of MEX, and if at some index i they are equal, we have the answer.

The problem is: how to calculate it efficiently? That my current code:

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> a(n);
        int a_max = 0;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            a_max = max(a_max, a[i]);
        }

        vector<int> mex_prefix(n);
        vector<int> mex_suffix(n);
        mex_prefix[0] = a[0] > 0 ? 0 : 1;
        mex_suffix[n - 1] = a[n - 1] > 0 ? 0 : 1;

        // Problematic part starts here
        set<int> s1{ a[0] };
        set<int> s2{ a[n - 1] };
        for (int i = 1, j = n - 2; i < n && j >= 0; ++i, --j) {
            s1.insert(a[i]);
            s2.insert(a[j]);

            for (int val = 0; val <= a_max + 1; ++val) {
                if (s1.find(val) == s1.end()) {
                    mex_prefix[i] = max(mex_prefix[i - 1], val);
                    break;
                }
            }

            for (int val = 0; val <= a_max + 1; ++val) {
                if (s2.find(val) == s2.end()) {
                    mex_suffix[j] = max(mex_suffix[j + 1], val);
                    break;
                }
            }
        }
        // End

        bool valid = false;
        int i = 0;
        for (; i < n - 1; ++i) {
            if (mex_prefix[i] == mex_suffix[i + 1]) {
                valid = true;
                break;
            }
        }

        if (!valid) {
            cout << -1 << '\n';
        }
        else {
            cout << 2 << '\n';
            cout << 1 << ' ' << i + 1 << '\n';
            cout << i + 2 << ' ' << n << '\n';
        }
    }
}

I will discuss it for prefix array, because building suffix array is analogous.

We set 0-th index of prefix array to valid MEX, and then we iterate through a array, while adding elements to set s1. At every a[i], we check whether it will increase the MEX on 0..i prefix. How? We iterate through all possible values (0 to max(a) + 1) and check if the current value was present in a suffix up to i. If it wasn't, then it can be MEX only if it's greater than MEX suffix up to previous index i - 1. If we find that value, then it's lowest value not present in suffix a[0..i].

The complexity of this it too big. It's like O(n * max(a) * logN) (due to using set to check if element exists in a till index i, and inserting elements to the set), which can result in more than 10^10 operations. How can we speed it up?

Answer 1

You present code for a typical "challenge" submission without ever spelling out the problem in the source code.
What's more, you miss the opportunity to declare a suggestively named business function.

Given a preceding introduction of MinimumEXcluded number and the solution idea (in the source (I agree with the result two parts are enough)), mex_prefix/mex_suffix are appropriately named;
n, a&a_max pick up the problem statement's designations.

I think "the problematic part" starts before the annotation:

With an empty (sub)sequence, MEX is 0.
Extending a sequence with one value changes MEX exactly when the value is the former MEX value: no need for special handling of last or first value.

You use two iteration variables to iterate the sequence "from both ends"; one would do using n-1 - i instead of j.
Using both to control loop termination looks redundant.

Inside this loop, there is one loop per direction to find the smallest value still excluded. Both could start at MEX (mex_???fix[i-1/j+1) as all smaller values are known to be in the subsequence.
From C++20, there seems to be a contains() for sets which I'd find more readable here.

When i&j meet or "cross", one can stop updating any non-lower MEX.
If they are equal, both i&j are suitable split positions.
Simpler and halving "additional memory" required is to just establish mex_prefix[] and look for a match looping the other direction keeping a MEX for the suffix up-to-date.

I'd handle a suitable split position right in the loop, using return to terminate, and put "the none found handling" simply after the loop. (I see two ways to keep statement nesting in check here: one is breaking the loop as you did. Alternatively, move the handling out of the current procedure with an additional procedure, or to the one call site.)

---

Comments on problem&approaches:
I think I need to calculate the prefix and suffix array of MEX
be aware you turned this into an XY problem.
(→ once you have a solution using those arrays, check if you now don't see a better solution to the original problem. (Like establishing just one and using early out in the pass in the other direction.) Time allowing, ponder if there is a lesson to take home…)

As MEX cannot exceed n+1, one can map any larger value to n+2 (on input already). (This does not really speed up innermost loops termination as there is guaranteed to be a value missing before.)(Depending on representation, this would help keeping histogram memory occupancy small, too.)

In addition to a_max, one could establish an a_min:
If greater than 0, any split works, as well as when a_max is 0.