codeforces-scrape

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

1779C.md (2768B)


      1 Source: https://codeforces.com/problemset/problem/1779/C
      2 
      3 C. Least Prefix Sum
      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 Baltic, a famous chess player who is also a mathematician, has an array $a_1,a_2, \ldots, a_n$, and he can perform the following operation several (possibly $0$) times:
     22 
     23 * Choose some index $i$ ($1 \leq i \leq n$);
     24 * multiply $a_i$ with $-1$, that is, set $a_i := -a_i$.
     25 
     26 Baltic's favorite number is $m$, and he wants $a_1 + a_2 + \cdots + a_m$ to be the smallest of all non-empty prefix sums. More formally, for each $k = 1,2,\ldots, n$ it should hold that $$a_1 + a_2 + \cdots + a_k \geq a_1 + a_2 + \cdots + a_m.$$
     27 
     28 Please note that multiple smallest prefix sums may exist and that it is only required that $a_1 + a_2 + \cdots + a_m$ is one of them.
     29 
     30 Help Baltic find the minimum number of operations required to make $a_1 + a_2 + \cdots + a_m$ the least of all prefix sums. It can be shown that a valid sequence of operations always exists.
     31 
     32 Input
     33 
     34 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10\,000$). The description of the test cases follows.
     35 
     36 The first line of each test case contains two integers $n$ and $m$ ($1 \leq m \leq n \leq 2\cdot 10^5$) — the size of Baltic's array and his favorite number.
     37 
     38 The second line contains $n$ integers $a_1,a_2, \ldots, a_n$ ($-10^9 \leq a_i \leq 10^9$) — the array.
     39 
     40 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.
     41 
     42 Output
     43 
     44 For each test case, print a single integer — the minimum number of required operations.
     45 
     46 Example
     47 
     48 Input
     49 
     50 ```
     51 6
     52 
     53 4 3
     54 
     55 -1 -2 -3 -4
     56 
     57 4 3
     58 
     59 1 2 3 4
     60 
     61 1 1
     62 
     63 1
     64 
     65 5 5
     66 
     67 -2 3 -5 1 -20
     68 
     69 5 2
     70 
     71 -2 3 -5 -5 -20
     72 
     73 10 4
     74 
     75 345875723 -48 384678321 -375635768 -35867853 -35863586 -358683842 -81725678 38576 -357865873
     76 ```
     77 
     78 Output
     79 
     80 ```
     81 1
     82 1
     83 0
     84 0
     85 3
     86 4
     87 ```
     88 
     89 Note
     90 
     91 In the first example, we perform the operation $a_4 := -a_4$. The array becomes $[-1,-2,-3,4]$ and the prefix sums, $[a_1, \ a_1+a_2, \ a_1+a_2+a_3, \ a_1+a_2+a_3+a_4]$, are equal to $[-1,-3,-6,-2]$. Thus $a_1 + a_2 + a_3=-6$ is the smallest of all prefix sums.
     92 
     93 In the second example, we perform the operation $a_3 := -a_3$. The array becomes $[1,2,-3,4]$ with prefix sums equal to $[1,3,0,4]$.
     94 
     95 In the third and fourth examples, $a_1 + a_2 + \cdots + a_m$ is already the smallest of the prefix sums — no operation needs to be performed.
     96 
     97 In the fifth example, a valid sequence of operations is:
     98 
     99 * $a_3 := -a_3$,
    100 * $a_2 := -a_2$,
    101 * $a_5 := -a_5$.
    102 
    103 The array becomes $[-2,-3,5,-5,20]$ and its prefix sums are $[-2,-5,0,-5,15]$. Note that $a_1+a_2=-5$ and $a_1+a_2+a_3+a_4=-5$ are both the smallest of the prefix sums (and this is a valid solution).