PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: satyam_343
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
Sets/sorting
PROBLEM:
You’re given an array A.
In one operation, you can choose a subarray and insert its MEX anywhere in A.
Find the minimum number of operations needed to be able to insert K.
EXPLANATION:
For a subarray to have MEX equal to K, it must contain (at least) one occurrence of each of 0, 1, 2, \ldots, K-1, and must not contain any occurrences of K.
First, suppose that K does not appear in A at all.
This then means that the MEX of any subarray of A will certainly be \le K.
In this case, clearly it’s optimal to just repeatedly keep choosing the entire array to operate on.
This is because the entire array has the largest MEX, so choosing the whole array will just keep giving us the next missing number - till we have at least one occurrence of each of 0, 1, 2, \ldots, K-1, at which point the next operation will give us K.
It’s quite obvious that this is optimal, since each operation advances us one step towards our goal of having every value in [0, K-1], and clearly it’s impossible to do better.
In particular, note that if there are D distinct elements among [0, K-1] present in the array, the answer is simply K+1-D.
Counting the number of distinct elements \lt K can be done quickly using a set, for example (or by sorting the array).
Next, let’s consider the case where K does exist in the array.
Suppose K appears at positions i_1, i_2, \ldots, i_m from left to right.
Observe that since the final subarray chosen to obtain a MEX of K cannot contain K itself, this subarray must lie entirely between some two consecutive appearances of K.
That is, the final subarray must lie entirely in [1, i_1-1], or in [i_1+1, i_2-1], or in [i_2+1, i_3-1], or so on till [i_m+1, N].
(Of course, the exact indices will change a little based on future insertions, but the overall idea is that the final subarray can never ‘cross’ a K).
This means we can simply solve for each ‘smaller’ subarray independently, pretending it’s an array without K, and then take the best answer among them all.
It’s easy to see that this is optimal, since a smaller subarray with D distinct elements \lt K surely needs at least (K-D) moves to obtain one copy of each element it’s missing (plus one for the final move to obtain K); and that can be obtained by operating within the subarray itself (so we don’t need to consider “cross-subarray” moves, since they don’t improve the answer anyway.)
TIME COMPLEXITY:
\mathcal{O}(N \log N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, k = map(int, input().split())
a = [k] + list(map(int, input().split())) + [k]
ans = n+1
prv = 0
have = set()
for i in range(1, n+2):
if a[i] == k:
ans = min(ans, k+1 - len(have))
have = set()
else:
if a[i] < k: have.add(a[i])
print(ans)