codeforces-scrape

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

2134C.md (3621B)


      1 Source: https://codeforces.com/problemset/problem/2134/C
      2 
      3 C. Even Larger
      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 An array is called good if, for every subarray$^{\text{∗}}$ of length at least $2$, the sum of the elements at even indices (with respect to the original array) is greater than or equal to the sum of the elements at odd indices. Array indexing starts from $1$.
     22 
     23 For example, the arrays $[3,8,4,4]$ and $[2,3,1,4,2]$ are good. The array $[0,2,4,1]$ is not because, in the subarray $[2,4,1]$, the elements at even indices in the original array are $2$ (index $2$) and $1$ (index $4$), while the only element at an odd index is $4$ (index $3$). Since $2 + 1 \lt 4$, the condition does not hold for this subarray.
     24 
     25 You are given an array of $n$ non-negative integers $a_1,a_2,\ldots,a_n$. In one operation, you can decrease any element in the array by $1$, but all elements must remain non-negative. Your task is to find the minimum number of operations needed to make the array $a$ good. It can be proved that it is possible to make the array good using a finite number of operations.
     26 
     27 $^{\text{∗}}$An array $b$ is a subarray of an array $a$ if $b$ can be obtained from $a$ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.
     28 
     29 Input
     30 
     31 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     32 
     33 The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the length of the array $a$.
     34 
     35 The second line of each test case contains $n$ non-negative integers $a_1,a_2,\ldots,a_n$ ($0 \le a_i \le 10^9$) — the elements of the array $a$.
     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, output a single integer in a new line — the minimum number of operations needed to make the array $a$ good.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 8
     49 
     50 4
     51 
     52 3 8 4 4
     53 
     54 4
     55 
     56 0 2 3 5
     57 
     58 2
     59 
     60 3 1
     61 
     62 5
     63 
     64 2 3 1 4 2
     65 
     66 4
     67 
     68 0 2 4 1
     69 
     70 5
     71 
     72 3 1 4 5 1
     73 
     74 11
     75 
     76 3 0 5 4 4 5 3 0 3 4 1
     77 
     78 12
     79 
     80 410748345 10753674 975233308 193331255 893457280 279719251 704970985 412553354 801228787 44181004 1000000000 3829103
     81 ```
     82 
     83 Output
     84 
     85 ```
     86 0
     87 1
     88 2
     89 0
     90 3
     91 6
     92 14
     93 4450984776
     94 ```
     95 
     96 Note
     97 
     98 In the first test case, the array $a$ is already good, so the answer is $0$. Below are the checks for each subarray:
     99 
    100 |  |  |  |  |
    101 | --- | --- | --- | --- |
    102 | Subarray | Even Index Sum | Odd Index Sum | Condition met? |
    103 | $[3,8]$ | $8$ | $3$ | Yes |
    104 | $[8,4]$ | $8$ | $4$ | Yes |
    105 | $[4,4]$ | $4$ | $4$ | Yes |
    106 | $[3,8,4]$ | $8$ | $3+4=7$ | Yes |
    107 | $[8,4,4]$ | $8+4 = 12$ | $4$ | Yes |
    108 | $[3,8,4,4]$ | $8+4=12$ | $3 + 4 = 7$ | Yes |
    109 
    110 In the second test case, the array $a$ is not good:
    111 
    112 |  |  |  |  |
    113 | --- | --- | --- | --- |
    114 | Subarray | Even Index Sum | Odd Index Sum | Condition met? |
    115 | $[0,2]$ | $2$ | $0$ | Yes |
    116 | $[2,3]$ | $2$ | $3$ | No |
    117 | $[3,5]$ | $5$ | $3$ | Yes |
    118 | $[0,2,3]$ | $2$ | $0+3=3$ | No |
    119 | $[2,3,5]$ | $2 + 5 = 7$ | $3$ | Yes |
    120 | $[0,2,3,5]$ | $2+5 = 7$ | $0+3 = 3$ | Yes |
    121 
    122 However, if we perform an operation on index $3$, the array becomes $[0,2,2,5]$ and is good now:
    123 
    124 |  |  |  |  |
    125 | --- | --- | --- | --- |
    126 | Subarray | Even Index Sum | Odd Index Sum | Condition met? |
    127 | $[0,2]$ | $2$ | $0$ | Yes |
    128 | $[2,2]$ | $2$ | $2$ | Yes |
    129 | $[2,5]$ | $5$ | $2$ | Yes |
    130 | $[0,2,2]$ | $2$ | $0+2=2$ | Yes |
    131 | $[2,2,5]$ | $2 + 5 = 7$ | $2$ | Yes |
    132 | $[0,2,2,5]$ | $2+5 = 7$ | $0+2 = 2$ | Yes |
    133 
    134 Therefore, the answer is $1$.