P5235 - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

You have an array A.
You can perform the following operation on it:

  • Choose a subarray A[l, r].
  • Let M denote the MEX of this subarray.
  • Replace any one element of the subarray by M.

For each K = 0, 1, 2, \ldots, N independently, find the minimum number of operations needed to make \text{MEX}(A) = K.

EXPLANATION:

Let M = \text{MEX}(A) be the initial MEX of A.
Obviously, for K = M the answer is just 0.

For other values of K, by definition we can have \text{MEX}(A) = K if and only if:

  • A contains at least one copy of each of 0, 1, 2, \ldots, K-1; and
  • A does not contain any copies of K.

To satisfy the first condition, we need to insert new elements into A (if they don’t yet exist), while to satisfy the second condition, we need to delete elements from A.

Each operation allows us to overwrite one element of the array, which corresponds to (at best) one insertion and one deletion (if we overwrite a to-be-deleted element with one that needs to be inserted.)

So,

  • Let c_K denote the number of copies of K present in the array.
  • Let m_K denote the number of elements in [0, K-1] that are missing from the array.
  • We then definitely need at least \max(c_K, m_K) operations to make the MEX of the array equal K.

Luckily, there always exists a sequence of \max(c_K, m_K) operations that will make \text{MEX}(A) = K, so this is exactly the answer!

Proof

While there exists a copy of K in the array, repeatedly perform the following operation:

  • Choose l = 1, r = N (so the entire array.)
    Then replace one copy of K with \text{MEX}(A).

This operation will be performed exactly c_K times before we run out of copies of K.

Now, if c_K \ge m_K, then the current MEX of the array will be exactly K: because the first m_K operations would’ve inserted all missing elements smaller than K one at a time; after which we only insert larger elements - so that once all copies of K are gone, the MEX will equal K.

Next, consider the case of c_K \lt m_K.
We’ve used c_K operations to remove copies of K entirely.
However, there are still missing elements that are smaller than K.

Let’s pick one copy of each existing value less than K and “freeze” it, meaning it won’t be touched in the future.
Now, repeat the following:

  • Choose the full array (so l = 1, r = N again).
    Note that the MEX is \lt K.
  • Choose any element that’s not frozen and replace it with \text{MEX}(A).
  • Freeze the newly added element.

It’s always possible to replace an unfrozen element in every operation (the only time we have all frozen elements is when the array is a permutation of [0, 1, \ldots, N-1] and the target MEX is N, in which case the MEX is already what we want.)

So, after another (m_K - c_K) operations (for a total of m_K operations), the MEX will become K.

We’ve hence used \max(m_K, c_K) operations to obtain a MEX of K, as claimed.

The only remaining part is actually computing the values m_K and c_K quickly.

For this,

  • c_K is the frequency of K.
    This can be found for all K \in [0, N] by just building a frequency table of the array in linear time.
  • m_K is the number of missing elements smaller than K.
    This can be computed as follows:
    • First compute all the c_K values.
    • Then, m_K equals the number of zeros among c_0, c_1, \ldots, c_{K-1}.
    • This can be found by maintaining prefix sums of the number of zeros in c (or just maintain a running sum as you iterate K.)

So, with \mathcal{O}(N) precomputation, we’re able to find both m_K and c_K in constant time for any given K.
This gives a linear-time solution.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    freq = [0]*(n+1)
    for x in a: freq[x] += 1
    
    empty = 0
    ans = [0]*(n+1)
    for k in range(n+1):
        ans[k] = max(empty, freq[k])
        empty += freq[k] == 0
    print(*ans)