codeforces-scrape

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

2271B.md (3301B)


      1 Source: https://codeforces.com/problemset/problem/2271/B
      2 
      3 B. MEX Game
      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 For a multiset $\mathcal{S}$ and a positive integer $k$, let $\operatorname{mex}_k(\mathcal{S})$ be the smallest non-negative integer that appears in $\mathcal{S}$ fewer than $k$ times. In particular, $\operatorname{mex}_1(\mathcal{S})$ is the usual $\operatorname{mex}$$^{\text{∗}}$ of $\mathcal{S}$.
     22 
     23 For example:
     24 
     25 * $\operatorname{mex}_1(\{0, 1, 1, 2\}) = 3$;
     26 * $\operatorname{mex}_2(\{0, 0, 1, 1, 1, 3\}) = 2$;
     27 * $\operatorname{mex}_2(\{0, 1, 1, 2\}) = 0$;
     28 * $\operatorname{mex}_2(\{0, 0, 1, 2\}) = 1$.
     29 
     30 You are given an even integer $n$, a positive integer $k$, and $n$ cards. The integer $a_i$ is written on the $i$-th card.
     31 
     32 Alice and Bob play the following game with these cards. Alice moves first, and the players alternate turns. On each turn, the current player takes any one of the remaining cards. The game ends when all $n$ cards have been taken, so each player ends up with exactly $\dfrac{n}{2}$ cards.
     33 
     34 Let $\mathcal{A}$ be the multiset of integers written on Alice's cards, and let $\mathcal{B}$ be the multiset of integers written on Bob's cards. Alice wins if $\operatorname{mex}_k(\mathcal{A}) \ne \operatorname{mex}_k(\mathcal{B})$, and Bob wins otherwise.
     35 
     36 Determine whether Alice wins if both players play optimally.
     37 
     38 $^{\text{∗}}$The minimum excluded (MEX) of a collection of integers $c_1, c_2, \ldots, c_m$ is defined as the smallest non-negative integer $x$ which does not occur in the collection $c$.
     39 
     40 Input
     41 
     42 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.
     43 
     44 The first line of each test case contains two integers $n$ and $k$ ($2 \le n \le 2 \cdot 10^5$, $n$ is even, $1 \le k \le n$) — the number of cards and the parameter of the game.
     45 
     46 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le n$) — the integers written on the cards.
     47 
     48 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     49 
     50 Output
     51 
     52 For each test case, output "YES" if Alice wins, and "NO" otherwise.
     53 
     54 You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
     55 
     56 Example
     57 
     58 Input
     59 
     60 ```
     61 5
     62 
     63 4 1
     64 
     65 2 0 0 1
     66 
     67 4 1
     68 
     69 0 1 0 1
     70 
     71 6 2
     72 
     73 1 2 0 1 0 0
     74 
     75 6 2
     76 
     77 0 0 1 1 2 2
     78 
     79 8 2
     80 
     81 0 1 1 0 0 2 0 1
     82 ```
     83 
     84 Output
     85 
     86 ```
     87 YES
     88 
     89 NO
     90 
     91 YES
     92 
     93 NO
     94 
     95 YES
     96 ```
     97 
     98 Note
     99 
    100 In the first example, Alice can take the card showing $1$ on her first turn and a card showing $0$ on her second turn. Then $\mathcal{A} = \{0, 1\}$ and $\mathcal{B} = \{0, 2\}$, so $\operatorname{mex}_1(\mathcal{A}) = 2$ and $\operatorname{mex}_1(\mathcal{B}) = 1$. It can be proven that Alice wins regardless of Bob's moves, so the answer is "YES".
    101 
    102 In the second example, the players can take cards in the following order: Alice takes $1$, Bob takes $1$, Alice takes $0$, and Bob takes $0$. Then $\mathcal{A} = \mathcal{B} = \{0, 1\}$ and $\operatorname{mex}_1(\mathcal{A}) = \operatorname{mex}_1(\mathcal{B}) = 2$. It can be proven that Bob wins if both players play optimally, so the answer is "NO".