Progressions Covering (Codeforces 1661D)
Tags: Greedy, data structures

You are given two arrays: an array $$$a$$$ consisting of $$$n$$$ zeros and an array $$$b$$$ consisting of $$$n$$$ integers.You can apply the following operation to the array $$$a$$$ an arbitrary number of times: choose some subsegment of $$$a$$$ of length $$$k$$$ and add the arithmetic progression $$$1, 2, \ldots, k$$$ to this subsegment — i. e. add $$$1$$$ to the first element of the subsegment, $$$2$$$ to the second element, and so on. The chosen subsegment should be inside the borders of the array $$$a$$$ (i.e., if the left border of the chosen subsegment is $$$l$$$, then the condition $$$1 \le l \le l + k - 1 \le n$$$ should be satisfied). Note that the progression added is always $$$1, 2, \ldots, k$$$ but not the $$$k, k - 1, \ldots, 1$$$ or anything else (i.e., the leftmost element of the subsegment always increases by $$$1$$$, the second element always increases by $$$2$$$ and so on).Your task is to find the minimum possible number of operations required to satisfy the condition $$$a_i \ge b_i$$$ for each $$$i$$$ from $$$1$$$ to $$$n$$$. Note that the condition $$$a_i \ge b_i$$$ should be satisfied for all elements at once.

Input: The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 3 \cdot 10^5$$$) — the number of elements in both arrays and the length of the subsegment, respectively.The second line of the input contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 10^{12}$$$), where $$$b_i$$$ is the $$$i$$$-th element of the array $$$b$$$.

Output: Print one integer — the minimum possible number of operations required to satisfy the condition $$$a_i \ge b_i$$$ for each $$$i$$$ from $$$1$$$ to $$$n$$$.

Note: Consider the first example. In this test, we don't really have any choice, so we need to add at least five progressions to make the first element equals $$$5$$$. The array $$$a$$$ becomes $$$[5, 10, 15]$$$.Consider the second example. In this test, let's add one progression on the segment $$$[1; 3]$$$ and two progressions on the segment $$$[4; 6]$$$. Then, the array $$$a$$$ becomes $$$[1, 2, 3, 2, 4, 6]$$$.

Sample Inputs:
3 3
5 4 6

6 3
1 2 3 2 2 3

6 3
1 2 4 1 2 3

7 3
50 17 81 25 42 39 96

Sample Outputs:
5

3

3

92

Solution (Python):
(n, k) = [*map(int, input().split())]
b = [*map(int, input().split())]
d = [0] * n
s = total = 0
nhsbw = 0
dhyd = 0
for i in range(n - 1, -1, -1):
    b[i] -= total
    if b[i] > 0:
        dd = min(k, i + 1)
        d[i] = (b[i] + dd - 1) // dd
    s += d[i] - (d[i + k] if i + k < n else 0)
    total += d[i] * dd - s
print(sum(d))

Solution (Python):
(n, k) = [*map(int, input().split())]
b = [*map(int, input().split())]
d = [0] * n
s = total = 0
for i in range(n - 1, -1, -1):
    b[i] -= total
    if b[i] > 0:
        dd = min(k, i + 1)
        d[i] = (b[i] + dd - 1) // dd
    s += d[i] - (d[i + k] if i + k < n else 0)
    total += d[i] * dd - s
print(sum(d))

Solution (Python):
def main():
    (n, k) = map(int, input().split())
    b = list(map(int, input().split()))
    temp = 0
    operations = [0] * n
    last = 0
    for i in range(n - 1, k - 1, -1):
        now = 0
        if i != n - 1:
            last -= temp
            now = last
            if i + k >= n:
                pass
            else:
                temp -= operations[i + k]
        delta = b[i] - now
        if delta <= 0:
            continue
        else:
            operations[i] = (delta + k - 1) // k
            temp += operations[i]
            last = operations[i] * k + now
    m = 0
    need = [0] * k
    for i in range(k - 1, -1, -1):
        if i != n - 1:
            last -= temp
            need[i] = max(0, b[i] - last)
            if i + k >= n:
                pass
            else:
                temp -= operations[i + k]
        else:
            need[i] = max(0, b[i])
    for i in range(k):
        m = max(m, (need[i] + i) // (i + 1))
    print(sum(operations) + m)
main()