Multitest Generator (Codeforces 1798E)
Tags: DP, brute force

Let's call an array $$$b_1, b_2, \ldots, b_m$$$ a test if $$$b_1 = m - 1$$$.Let's call an array $$$b_1, b_2, \ldots, b_m$$$ a multitest if the array $$$b_2, b_3, \ldots, b_m$$$ can be split into $$$b_1$$$ non-empty subarrays so that each of these subarrays is a test. Note that each element of the array must be included in exactly one subarray, and the subarrays must consist of consecutive elements.Let's define the function $$$f$$$ from the array $$$b_1, b_2, \ldots, b_m$$$ as the minimum number of operations of the form "Replace any $$$b_i$$$ with any non-negative integer $$$x$$$", which needs to be done so that the array $$$b_1, b_2, \ldots, b_m$$$ becomes a multitest.You are given an array of positive integers $$$a_1, a_2, \ldots, a_n$$$. For each $$$i$$$ from $$$1$$$ to $$$n - 1$$$, find $$$f([a_i, a_{i+1}, \ldots, a_n])$$$.Below are some examples of tests and multitests.   Tests: $$$[\underline{1}, 5]$$$, $$$[\underline{2}, 2, 2]$$$, $$$[\underline{3}, 4, 1, 1]$$$, $$$[\underline{5}, 0, 0, 0, 0, 0]$$$, $$$[\underline{7}, 1, 2, 3, 4, 5, 6, 7]$$$, $$$[\underline{0}]$$$. These arrays are tests since their first element (underlined) is equal to the length of the array minus one.  Multitests: $$$[1, \underline{\underline{1}, 1}]$$$, $$$[2, \underline{\underline{3}, 0, 0, 1}, \underline{\underline{1}, 12}]$$$, $$$[3, \underline{\underline{2}, 2, 7}, \underline{\underline{1}, 1}, \underline{\underline{3}, 4, 4, 4}]$$$, $$$[4, \underline{\underline{0}}, \underline{\underline{3}, 1, 7, 9}, \underline{\underline{4}, 2, 0, 0, 9}, \underline{\underline{1}, 777}]$$$. Underlined are the subarrays after the split, and double underlined are the first elements of each subarray. 

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 300\,000$$$). The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 300\,000$$$) — the length of the array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 300\,000$$$) — elements of the array $$$a$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$300\,000$$$.

Output: For each test case print $$$n - 1$$$ numbers — $$$f([a_i, a_{i+1}, \ldots, a_n])$$$ for each $$$i$$$ from $$$1$$$ to $$$n - 1$$$.

Note: In the first test case of the first test the array $$$[1, 2, 1, 7]$$$ is a multitest since the array $$$[2, 1, 7]$$$ is a test. The array $$$[2, 1, 7]$$$ is not a multitest, but after replacing the first number with $$$1$$$, an array $$$[1, 1, 7]$$$ is obtained, which is a multitest. The array $$$[1, 7]$$$ is also not a multitest, but the array $$$[1, 0]$$$ is, so $$$f([1, 7]) = 1$$$.In the second test case of first test, for $$$i = 2$$$, $$$f([a_i, a_{i+1}, \ldots, a_n]) = f([1, 3, 1, 2, 1, 1]) = 1$$$, since the array itself is not a multitest, but after replacing the second element with $$$4$$$ you get multitest.In the third test case of first test, for $$$i = 1$$$, $$$f([a_i, a_{i+1}, \ldots, a_n]) = f([2, 7, 1, 1]) = 1$$$, since the array itself is not a multitest, but after replacing the second element with $$$0$$$ you get multitest.The second test is an array composed of all the numbers of the first test. Therefore $$$f([a_1, a_2, \ldots, a_n])$$$ naturally equals to $$$0$$$.

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

1
19
3 4 1 2 1 7 7 3 1 3 1 2 1 1 4 2 7 1 1

Sample Outputs:
0 1 1 
0 1 1 0 1 1 
1 1 1

0 0 1 1 1 1 1 1 1 0 1 0 1 0 2 1 1 1

Solution (Python):
N = 300777
a = [0] * N
go = [0] * N
good_chain = [0] * N
chain_depth = [0] * N
suf_max_chain_depth = [0] * N
ans = ''
for _ in range(int(input())):
    n = int(input())
    a = [0] + list(map(int, input().split()))
    chain_depth[n + 1] = 0
    suf_max_chain_depth[n + 1] = 0
    curr_max_chain_depth = 0
    for i in range(n, 0, -1):
        go[i] = i + a[i] + 1
        if go[i] == n + 1 or (go[i] <= n and good_chain[go[i]]):
            good_chain[i] = True
        else:
            good_chain[i] = False
        chain_depth[i] = 1 + chain_depth[min(go[i], n + 1)]
        suf_max_chain_depth[i] = 1 + curr_max_chain_depth
        if go[i] <= n + 1:
            suf_max_chain_depth[i] = max(suf_max_chain_depth[i], 1 + suf_max_chain_depth[go[i]])
        if good_chain[i]:
            curr_max_chain_depth = max(curr_max_chain_depth, chain_depth[i])
    for i in range(1, n):
        if good_chain[i + 1] and chain_depth[i + 1] == a[i]:
            ans += '0 '
        elif good_chain[i + 1] or suf_max_chain_depth[i + 1] >= a[i]:
            ans += '1 '
        else:
            ans += '2 '
    ans += '\n'
print(ans)

Solution (Python):
N = 300777
a = [0] * N
go = [0] * N
good_chain = [0] * N
chain_depth = [0] * N
suf_max_chain_depth = [0] * N
ans = ''
for _ in range(int(input())):
    n = int(input())
    a = [0] + list(map(int, input().split()))
    chain_depth[n + 1] = 0
    suf_max_chain_depth[n + 1] = 0
    curr_max_chain_depth = 0
    for i in range(n, 0, -1):
        go[i] = i + a[i] + 1
        if go[i] == n + 1 or (go[i] <= n and good_chain[go[i]]):
            good_chain[i] = True
        else:
            good_chain[i] = False
        chain_depth[i] = 1 + chain_depth[min(go[i], n + 1)]
        suf_max_chain_depth[i] = 1 + curr_max_chain_depth
        if go[i] <= n + 1:
            suf_max_chain_depth[i] = max(suf_max_chain_depth[i], 1 + suf_max_chain_depth[go[i]])
        if good_chain[i]:
            curr_max_chain_depth = max(curr_max_chain_depth, chain_depth[i])
    for i in range(1, n):
        if good_chain[i + 1] and chain_depth[i + 1] == a[i]:
            ans += '0 '
        elif good_chain[i + 1] or suf_max_chain_depth[i + 1] >= a[i]:
            ans += '1 '
        else:
            ans += '2 '
    ans += '\n'
print(ans)

Solution (Python):
N = 300777
a = [0] * N
go = [0] * N
good_chain = [0] * N
chain_depth = [0] * N
suf_max_chain_depth = [0] * N
ans = ''
for _ in range(int(input())):
    n = int(input())
    a = [0] + list(map(int, input().split()))
    chain_depth[n + 1] = 0
    suf_max_chain_depth[n + 1] = 0
    curr_max_chain_depth = 0
    for i in range(n, 0, -1):
        go[i] = i + a[i] + 1
        if go[i] == n + 1 or (go[i] <= n and good_chain[go[i]]):
            good_chain[i] = True
        else:
            good_chain[i] = False
        chain_depth[i] = 1 + chain_depth[min(go[i], n + 1)]
        suf_max_chain_depth[i] = 1 + curr_max_chain_depth
        if go[i] <= n + 1:
            suf_max_chain_depth[i] = max(suf_max_chain_depth[i], 1 + suf_max_chain_depth[go[i]])
        if good_chain[i]:
            curr_max_chain_depth = max(curr_max_chain_depth, chain_depth[i])
    for i in range(1, n):
        if good_chain[i + 1] and chain_depth[i + 1] == a[i]:
            ans += '0 '
        elif good_chain[i + 1] or suf_max_chain_depth[i + 1] >= a[i]:
            ans += '1 '
        else:
            ans += '2 '
    ans += '\n'
print(ans)