codeforces-scrape

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

1738B.md (2273B)


      1 Source: https://codeforces.com/problemset/problem/1738/B
      2 
      3 B. Prefix Sum Addicts
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Suppose $a_1, a_2, \dots, a_n$ is a sorted integer sequence of length $n$ such that $a_1 \leq a_2 \leq \dots \leq a_n$.
     22 
     23 For every $1 \leq i \leq n$, the prefix sum $s_i$ of the first $i$ terms $a_1, a_2, \dots, a_i$ is defined by $$ s_i = \sum_{k=1}^i a_k = a_1 + a_2 + \dots + a_i. $$
     24 
     25 Now you are given the last $k$ terms of the prefix sums, which are $s_{n-k+1}, \dots, s_{n-1}, s_{n}$. Your task is to determine whether this is possible.
     26 
     27 Formally, given $k$ integers $s_{n-k+1}, \dots, s_{n-1}, s_{n}$, the task is to check whether there is a sequence $a_1, a_2, \dots, a_n$ such that
     28 
     29 1. $a_1 \leq a_2 \leq \dots \leq a_n$, and
     30 2. $s_i = a_1 + a_2 + \dots + a_i$ for all $n-k+1 \leq i \leq n$.
     31 
     32 Input
     33 
     34 Each test contains multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases. The following lines contain the description of each test case.
     35 
     36 The first line of each test case contains two integers $n$ ($1 \leq n \leq 10^5$) and $k$ ($1 \leq k \leq n$), indicating the length of the sequence $a$ and the number of terms of prefix sums, respectively.
     37 
     38 The second line of each test case contains $k$ integers $s_{n-k+1}, \dots, s_{n-1}, s_{n}$ ($-10^9 \leq s_i \leq 10^9$ for every $n-k+1 \leq i \leq n$).
     39 
     40 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     41 
     42 Output
     43 
     44 For each test case, output "YES" (without quotes) if it is possible and "NO" (without quotes) otherwise.
     45 
     46 You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 4
     54 
     55 5 5
     56 
     57 1 2 3 4 5
     58 
     59 7 4
     60 
     61 -6 -5 -3 0
     62 
     63 3 3
     64 
     65 2 3 4
     66 
     67 3 2
     68 
     69 3 4
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 Yes
     76 Yes
     77 No
     78 No
     79 ```
     80 
     81 Note
     82 
     83 In the first test case, we have the only sequence $a = [1, 1, 1, 1, 1]$.
     84 
     85 In the second test case, we can choose, for example, $a = [-3, -2, -1, 0, 1, 2, 3]$.
     86 
     87 In the third test case, the prefix sums define the only sequence $a = [2, 1, 1]$, but it is not sorted.
     88 
     89 In the fourth test case, it can be shown that there is no sequence with the given prefix sums.