Pekora and Trampoline (Codeforces 1491C)
Tags: Greedy, data structures

There is a trampoline park with $$$n$$$ trampolines in a line. The $$$i$$$-th of which has strength $$$S_i$$$.Pekora can jump on trampolines in multiple passes. She starts the pass by jumping on any trampoline of her choice. If at the moment Pekora jumps on trampoline $$$i$$$, the trampoline will launch her to position $$$i + S_i$$$, and $$$S_i$$$ will become equal to $$$\max(S_i-1,1)$$$. In other words, $$$S_i$$$ will decrease by $$$1$$$, except of the case $$$S_i=1$$$, when $$$S_i$$$ will remain equal to $$$1$$$. If there is no trampoline in position $$$i + S_i$$$, then this pass is over. Otherwise, Pekora will continue the pass by jumping from the trampoline at position $$$i + S_i$$$ by the same rule as above.Pekora can't stop jumping during the pass until she lands at the position larger than $$$n$$$ (in which there is no trampoline). Poor Pekora!Pekora is a naughty rabbit and wants to ruin the trampoline park by reducing all $$$S_i$$$ to $$$1$$$. What is the minimum number of passes she needs to reduce all $$$S_i$$$ to $$$1$$$?

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases.The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 5000$$$) — the number of trampolines.The second line of each test case contains $$$n$$$ integers $$$S_1, S_2, \dots, S_n$$$ ($$$1 \le S_i \le 10^9$$$), where $$$S_i$$$ is the strength of the $$$i$$$-th trampoline.It's guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$5000$$$.

Output: For each test case, output a single integer — the minimum number of passes Pekora needs to do to reduce all $$$S_i$$$ to $$$1$$$.

Note: For the first test case, here is an optimal series of passes Pekora can take. (The bolded numbers are the positions that Pekora jumps into during these passes.)  $$$[1,4,\textbf{2},2,\textbf{2},2,\textbf{2}]$$$  $$$[1,\textbf{4},1,2,1,\textbf{2},1]$$$  $$$[1,\textbf{3},1,2,\textbf{1},\textbf{1},\textbf{1}]$$$  $$$[1,\textbf{2},1,\textbf{2},1,\textbf{1},\textbf{1}]$$$ For the second test case, the optimal series of passes is show below.  $$$[\textbf{2},3]$$$  $$$[1,\textbf{3}]$$$  $$$[1,\textbf{2}]$$$ For the third test case, all $$$S_i$$$ are already equal to $$$1$$$.

Sample Inputs:
3
7
1 4 2 2 2 2 2
2
2 3
5
1 1 1 1 1

Sample Outputs:
4
3
0

Solution (Python):
import math, collections, sys, math, bisect, inspect, os, io
if os.path.exists('/home/debug.h'):

    def dbg(x):
        frame = inspect.currentframe()
        frame = inspect.getouterframes(frame)[1]
        string = inspect.getframeinfo(frame[0]).code_context[0].strip()
        args = string[string.find('(') + 1:-1].split(',')
        names = []
        for i in args:
            if i.find('=') != -1:
                names.append(i.split('=')[1].strip())
            else:
                names.append(i)
        print(names, ' : ', x, file=sys.stderr)
else:

    def dbg(x):
        pass

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    free = 0
    dif = [0] * (n + 10)
    for i in range(n):
        free += dif[i]
        extra = max(0, a[i] - 1 - free)
        ans += extra
        r = min(a[i] + i + 1, n)
        l = min(i + 2, n)
        dif[r] -= 1
        dif[l] += 1
        total = free + extra - a[i] + 1
        dif[i + 1] += total
        dif[i + 2] -= total
    print(ans)
    return
for _ in range(int(input())):
    solve()

Solution (Python):
t = int(input())
while t:
    t -= 1
    n = int(input())
    arr = list(map(int, input().split()))
    c = [0 for i in range(n)]
    ans = 0
    for i in range(n):
        if i > 0:
            c[i] += c[i - 1]
        if c[i] <= arr[i] - 1:
            ans += arr[i] - 1 - c[i]
        if arr[i] > 1:
            if i + 2 < n:
                c[i + 2] += 1
            if i + arr[i] + 1 < n:
                c[i + arr[i] + 1] += -1
        if c[i] > arr[i] - 1:
            extra = c[i] - arr[i] + 1
            if i + 1 < n:
                c[i + 1] += extra
            if i + 2 < n:
                c[i + 2] += -extra
    print(ans)

Solution (Python):
t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    g = [0] * (n + 5)
    las = 0
    for i in range(n):
        tmp = g[i] + las
        las = tmp
        if tmp > a[i] - 1:
            g[i + 1] += tmp - a[i] + 1
            g[i + 2] -= tmp - a[i] + 1
        else:
            ans += a[i] - 1 - tmp
        if i + 2 <= min(n, i + 1 + a[i]):
            g[i + 2] += 1
            g[min(n, i + a[i] + 1)] -= 1
    print(ans)