codeforces-scrape

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

2262A1.md (2882B)


      1 Source: https://codeforces.com/problemset/problem/2262/A1
      2 
      3 A1. Floor of MEX (Easy Version)
      4 
      5 time limit per test
      6 
      7 2 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 This is the easy version of the problem. The difference between the versions is that in this version, you only need to find one subset that satisfies the constraints. You can hack only if you solved all versions of this problem.
     22 
     23 Let $$ f(S,x)=\text{mex}\left(\left\{\left\lfloor \frac{y}{x}\right\rfloor : y\in S\right\}\right), $$ where $S$ is a set of non-negative integers and $x$ is a positive integer. $^{\text{∗}}$
     24 
     25 Farmer John chooses a (possibly empty) subset $A\subseteq \{0,1,\ldots,n-1\}$. He then constructs an array $a$ of length $n$, where $a_k = f(A,k)$ for every $1\le k\le n$.
     26 
     27 Bessie, being a mischievous cow, hides the set $A$. Farmer John is left only with the array $a_1,a_2,\ldots,a_n$.
     28 
     29 Your task is to construct any (possibly empty) subset $B\subseteq \{0,1,\ldots,n-1\}$ such that $f(B,k)=a_k$ for every $1 \le k \le n$. Farmer John will only give you arrays where such a $B$ exists.
     30 
     31 $^{\text{∗}}$$\operatorname{mex}(c)$ denotes the minimum excluded (MEX)$^{\text{∗}}$ of the collection $c$. (in this case, the minimum non-negative integer not present in the set)
     32 
     33 Input
     34 
     35 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.
     36 
     37 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 10^5$).
     38 
     39 The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0 \leq a_i \leq n$).
     40 
     41 You will only be given arrays where there exists $B \subseteq \{0,1,\ldots,n-1\}$ such that $f(B,k)=a_k$ for every $1 \le k \le n$.
     42 
     43 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     44 
     45 Output
     46 
     47 For each test case, output two lines.
     48 
     49 On the first line, output an integer $m$ — the size of the set $B$.
     50 
     51 On the second line, output $m$ distinct integers $b_1,b_2,\ldots,b_m$ — the elements of $B$. If $m=0$, the second line should be empty.
     52 
     53 The elements of $B$ may be printed in any order.
     54 
     55 If there are multiple solutions, you may output any of them.
     56 
     57 Example
     58 
     59 Input
     60 
     61 ```
     62 3
     63 
     64 6
     65 
     66 0 3 2 2 2 1
     67 
     68 5
     69 
     70 2 1 1 1 1
     71 
     72 6
     73 
     74 1 2 1 1 1 1
     75 ```
     76 
     77 Output
     78 
     79 ```
     80 5
     81 
     82 1 2 3 4 5
     83 
     84 2
     85 
     86 0 1
     87 
     88 2
     89 
     90 0 2
     91 ```
     92 
     93 Note
     94 
     95 For the first test case, one possible answer is $$ B=\{1,2,3,4,5\}. $$ Then $$ f(B,1)=\text{mex}(\{1,2,3,4,5\})=0, $$ $$ f(B,2)=\text{mex}(\{0,1,2\})=3, $$ and $$ f(B,3)=f(B,4)=f(B,5)=2. $$ Finally, $$ f(B,6)=\text{mex}(\{0\})=1. $$ Thus the array is $[0,3,2,2,2,1]$.
     96 
     97 For the second test case, one possible answer is $$ B=\{0,1\}. $$ Then $f(B,1)=2$, and for every $2\le k\le 5$, we have $$ \left\{\left\lfloor y/k\right\rfloor : y\in B\right\}=\{0\}, $$ so $f(B,k)=1$. Therefore, the array is $[2,1,1,1,1]$.