codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.