codeforces-scrape

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

1943A.md (2386B)


      1 Source: https://codeforces.com/problemset/problem/1943/A
      2 
      3 A. MEX Game 1
      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 Alice and Bob play yet another game on an array $a$ of size $n$. Alice starts with an empty array $c$. Both players take turns playing, with Alice starting first.
     22 
     23 On Alice's turn, she picks one element from $a$, appends that element to $c$, and then deletes it from $a$.
     24 
     25 On Bob's turn, he picks one element from $a$, and then deletes it from $a$.
     26 
     27 The game ends when the array $a$ is empty. Game's score is defined to be the MEX$^\dagger$ of $c$. Alice wants to maximize the score while Bob wants to minimize it. Find game's final score if both players play optimally.
     28 
     29 $^\dagger$ The $\operatorname{MEX}$ (minimum excludant) of an array of integers is defined as the smallest non-negative integer which does not occur in the array. For example:
     30 
     31 * The MEX of $[2,2,1]$ is $0$, because $0$ does not belong to the array.
     32 * The MEX of $[3,1,0,1]$ is $2$, because $0$ and $1$ belong to the array, but $2$ does not.
     33 * The MEX of $[0,3,1,2]$ is $4$, because $0$, $1$, $2$ and $3$ belong to the array, but $4$ does not.
     34 
     35 Input
     36 
     37 Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 2 \cdot 10^4$) — the number of test cases. The description of the test cases follows.
     38 
     39 The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$).
     40 
     41 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \lt n$).
     42 
     43 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     44 
     45 Output
     46 
     47 For each test case, find game's score if both players play optimally.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 3
     55 
     56 4
     57 
     58 0 0 1 1
     59 
     60 4
     61 
     62 0 1 2 3
     63 
     64 2
     65 
     66 1 1
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 2
     73 1
     74 0
     75 ```
     76 
     77 Note
     78 
     79 In the first test case, a possible game with a score of $2$ is as follows:
     80 
     81 1. Alice chooses the element $1$. After this move, $a=[0,0,1]$ and $c=[1]$.
     82 2. Bob chooses the element $0$. After this move, $a=[0,1]$ and $c=[1]$.
     83 3. Alice chooses the element $0$. After this move, $a=[1]$ and $c=[1,0]$.
     84 4. Bob chooses the element $1$. After this move, $a=[\,]$ and $c=[1,0]$.
     85 
     86 At the end, $c=[1,0]$, which has a MEX of $2$. Note that this is an example game and does not necessarily represent the optimal strategy for both players.