1656B.md (1963B)
1 Source: https://codeforces.com/problemset/problem/1656/B 2 3 B. Subtract Operation 4 5 time limit per test 6 7 1 second 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 You are given a list of $n$ integers. You can perform the following operation: you choose an element $x$ from the list, erase $x$ from the list, and subtract the value of $x$ from all the remaining elements. Thus, in one operation, the length of the list is decreased by exactly $1$. 22 23 Given an integer $k$ ($k \gt 0$), find if there is some sequence of $n-1$ operations such that, after applying the operations, the only remaining element of the list is equal to $k$. 24 25 Input 26 27 The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. Description of the test cases follows. 28 29 The first line of each test case contains two integers $n$ and $k$ ($2 \leq n \leq 2\cdot 10^5$, $1 \leq k \leq 10^9$), the number of integers in the list, and the target value, respectively. 30 31 The second line of each test case contains the $n$ integers of the list $a_1, a_2, \ldots, a_n$ ($-10^9 \leq a_i \leq 10^9$). 32 33 It is guaranteed that the sum of $n$ over all test cases is not greater that $2 \cdot 10^5$. 34 35 Output 36 37 For each test case, print YES if you can achieve $k$ with a sequence of $n-1$ operations. Otherwise, print NO. 38 39 You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as a positive answer). 40 41 Example 42 43 Input 44 45 ``` 46 4 47 48 4 5 49 50 4 2 2 7 51 52 5 4 53 54 1 9 1 3 4 55 56 2 17 57 58 17 0 59 60 2 17 61 62 18 18 63 ``` 64 65 Output 66 67 ``` 68 YES 69 NO 70 YES 71 NO 72 ``` 73 74 Note 75 76 In the first example we have the list $\{4, 2, 2, 7\}$, and we have the target $k = 5$. One way to achieve it is the following: first we choose the third element, obtaining the list $\{2, 0, 5\}$. Next we choose the first element, obtaining the list $\{-2, 3\}$. Finally, we choose the first element, obtaining the list $\{5\}$.