2236D.md (2648B)
1 Source: https://codeforces.com/problemset/problem/2236/D 2 3 D. Brand New Tatar TV Show 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 Dabir and Egor were not satisfied with the fame from the previous episode, so they decided to make another TV show: the guys play their favorite game on an array $a$ with their favorite integer $k$. 22 23 Dabir moves first. On the first move, any element from the array can be chosen and removed. Let the previous chosen element be equal to $x$. Then on the current move, except the very first one, a player must choose an element $y$ from the array such that $0 \leq y - x \leq k$ and remove it from the array. The player who cannot make a move loses. 24 25 But since this was not just a game, but a real show-match, Arseniy (aka MAKAN) — the main celebrity of Omsk was invited again. As a guest celebrity, Arseniy was given the opportunity to make the first move in this match, that is, to make the very first move in the game instead of Dabir. However, it turns out Arseniy is a fan of Egor, so he wants his first move to guarantee Egor a winning strategy against any response from Dabir. 26 27 Determine whether Arseniy can make the first move for Dabir so that, no matter how Dabir plays, Egor wins. 28 29 Input 30 31 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. 32 33 The first line of each test case contains two integers $n$ and $k$ ($1 \leq n, k \leq 2 \cdot 10^5$) — the length of the array and the favorite integer of Dabir and Egor. 34 35 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$). 36 37 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 38 39 Output 40 41 For each test case, if there exists such a first move that with optimal play by both players Egor wins, output "YES", otherwise output "NO". 42 43 You can output "YES" and "NO" in any case (for example, "yES", "yes", and "Yes" will be accepted). 44 45 Example 46 47 Input 48 49 ``` 50 7 51 52 5 1 53 54 3 3 3 3 3 55 56 3 1 57 58 1 1 2 59 60 2 2 61 62 2 1 63 64 4 1 65 66 3 3 3 3 67 68 4 3 69 70 2 2 2 1 71 72 4 1 73 74 1 3 1 1 75 76 5 1 77 78 5 1 5 1 5 79 ``` 80 81 Output 82 83 ``` 84 NO 85 86 YES 87 88 YES 89 90 YES 91 92 YES 93 94 NO 95 96 YES 97 ``` 98 99 Note 100 101 In the first example, the only possible option is to choose the integer $3$. After that, the array [$3, 3, 3, 3$] remains. Then Egor moves, then Dabir, and so on. Dabir will take the last $3$, so Arseniy cannot choose a first move that makes Egor win. 102 103 In the second example, Arseniy can choose the integer $1$ as the first move. Then Egor will choose the integer $2$, and Dabir will have no valid moves left, so Egor wins.