codeforces-scrape

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

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.