2183B.md (3063B)
1 Source: https://codeforces.com/problemset/problem/2183/B 2 3 B. Yet Another MEX Problem 4 5 time limit per test 6 7 1.5 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given an array $a$ of length $n$, and an integer $k$. Let $f(l,r)$ be the value of $\operatorname{mex}(a_l,a_{l+1},\ldots,a_r)$$^{\text{∗}}$. You want to perform the following operation $n-k+1$ times: 22 23 * Let the current length of the sequence be $|a|$. You need to find an interval $[l, r]$ of length $k$ such that $\operatorname{max}_{i=1}^{|a|-k+1} f(i, i+k-1) = f(l, r).$ In other words, you need to select a window of size $k$ such that among all windows of size $k$, the window you selected has the maximum $\operatorname{mex}$. If multiple $[l,r]$ exist, you may select any. Then, you must select any integer $i$ such that $l \leq i \leq r$, and delete $a_i$ from $a$. That is, your new sequence will be $[a_1, a_2, \ldots, a_{i-1}, a_{i+1}, a_{i+2}, \ldots, a_n]$. 24 25 For example, in the array $[1,2,0,1,3,0]$ with $k=3$, the two possible $(l,r)$ pairs are $(1,3)$ and $(2,4)$ (since they each have $\operatorname{mex} 3$, which is the maximum among all windows of size $3$). Therefore, you can remove any one of the indices $1,2,3,4$ in your next move. 26 27 After $n - k + 1$ operations, you will have a sequence of length $k-1$. Your objective is to maximize the $\operatorname{mex}$ of the remaining elements. Please output the maximum $\operatorname{mex}$ possible. 28 29 $^{\text{∗}}$The minimum excluded (MEX) of a collection of integers $c_1, c_2, \ldots, c_k$ is defined as the smallest non-negative integer $x$ which does not occur in the collection $c$. 30 31 Input 32 33 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 34 35 The first line of each test case contains two positive integers $n$ and $k$ ($2 \le k \le n \le 2 \cdot 10^5$). 36 37 The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0 \le a_i \le n$). 38 39 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 40 41 Output 42 43 Output a single non-negative integer representing your answer. 44 45 Example 46 47 Input 48 49 ``` 50 5 51 52 3 3 53 54 0 0 0 55 56 4 2 57 58 0 2 1 3 59 60 5 3 61 62 0 1 2 1 0 63 64 6 2 65 66 0 1 0 1 2 0 67 68 7 5 69 70 0 1 2 4 0 3 1 71 ``` 72 73 Output 74 75 ``` 76 1 77 78 1 79 80 2 81 82 1 83 84 4 85 ``` 86 87 Note 88 89 In the first test case, we can select the interval $[1,3]$. Then, delete $a_2$ to obtain $[0,0]$. The process terminates, and the $\operatorname{mex}$ of the remaining elements is $1$. 90 91 In the third test case, we can perform the following operations: 92 93 * Select $i=1,j=3$. This is allowed because the $\operatorname{mex}$ of all windows of size $3$ is $3,0,3$, and the window $[1,3]$ has a $\operatorname{mex}$ of $3$, which is the largest. Then, remove $a_2$. The sequence is now $[0,2,1,0]$. 94 * Select $i=2,j=4$. Then, remove $a_2$. The sequence is now $[0,1,0]$. 95 * Select $i=1,j=3$. Then, remove $a_1$. The sequence is now $[1,0]$. The process terminates, and the final $\operatorname{mex}$ is $2$.