codeforces-scrape

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

2123E.md (2056B)


      1 Source: https://codeforces.com/problemset/problem/2123/E
      2 
      3 E. MEX Count
      4 
      5 time limit per test
      6 
      7 3 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 Define the $\mathrm{MEX}$ (minimum excluded value) of an array to be the smallest nonnegative integer not present in the array. For example,
     22 
     23 * $\mathrm{MEX}([2, 2, 1]) = 0$ because $0$ is not in the array.
     24 * $\mathrm{MEX}([3, 1, 0, 1]) = 2$ because $0$ and $1$ are in the array but $2$ is not.
     25 * $\mathrm{MEX}([0, 3, 1, 2]) = 4$ because $0$, $1$, $2$, and $3$ are in the array but $4$ is not.
     26 
     27 You are given an array $a$ of size $n$ of nonnegative integers.
     28 
     29 For all $k$ ($0\leq k \leq n$), count the number of possible values of $\mathrm{MEX}(a)$ after removing exactly $k$ values from $a$.
     30 
     31 Input
     32 
     33 The first line contains an integer $t$ ($1\leq t\leq 10^4$)  — the number of test cases.
     34 
     35 The first line of each test case contains one integer $n$ ($1\leq n\leq 2\cdot 10^5$) — the size of the array $a$.
     36 
     37 The second line of each test case contains $n$ integers, $a_1,a_2,\dots,a_n$ ($0\leq a_i\leq 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 For each test case, output a single line containing $n+1$ integers — the number of possible values of $\mathrm{MEX}(a)$ after removing exactly $k$ values, for $k=0,1,\dots,n$.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 5
     51 
     52 5
     53 
     54 1 0 0 1 2
     55 
     56 6
     57 
     58 3 2 0 4 5 1
     59 
     60 6
     61 
     62 1 2 0 1 3 2
     63 
     64 4
     65 
     66 0 3 4 1
     67 
     68 5
     69 
     70 0 0 0 0 0
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 1 2 4 3 2 1
     77 1 6 5 4 3 2 1
     78 1 3 5 4 3 2 1
     79 1 3 3 2 1
     80 1 1 1 1 1 1
     81 ```
     82 
     83 Note
     84 
     85 In the first sample, consider $k=1$. If you remove a $0$, then you get the following array:
     86 
     87 |  |  |  |  |
     88 | --- | --- | --- | --- |
     89 | 1 | 0 | 1 | 2 |
     90 
     91 So we get $\mathrm{MEX}(a) = 3$. Alternatively, if you remove the $2$, then you get the following array:
     92 
     93 |  |  |  |  |
     94 | --- | --- | --- | --- |
     95 | 1 | 0 | 0 | 1 |
     96 
     97 So we get $\mathrm{MEX}(a) = 2$. It can be shown that these are the only possible values of $\mathrm{MEX}(a)$ after removing exactly one value. So the output for $k=1$ is $2$.