codeforces-scrape

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

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\}$.