Blocking Elements (Codeforces 1918D)
Tags: Implement, two pointers

You are given an array of numbers $$$a_1, a_2, \ldots, a_n$$$. Your task is to block some elements of the array in order to minimize its cost. Suppose you block the elements with indices $$$1 \leq b_1 < b_2 < \ldots < b_m \leq n$$$. Then the cost of the array is calculated as the maximum of:   the sum of the blocked elements, i.e., $$$a_{b_1} + a_{b_2} + \ldots + a_{b_m}$$$.  the maximum sum of the segments into which the array is divided when the blocked elements are removed. That is, the maximum sum of the following ($$$m + 1$$$) subarrays: [$$$1, b_1 − 1$$$], [$$$b_1 + 1, b_2 − 1$$$], [$$$\ldots$$$], [$$$b_{m−1} + 1, b_m - 1$$$], [$$$b_m + 1, n$$$] (the sum of numbers in a subarray of the form [$$$x,x − 1$$$] is considered to be $$$0$$$). For example, if $$$n = 6$$$, the original array is [$$$1, 4, 5, 3, 3, 2$$$], and you block the elements at positions $$$2$$$ and $$$5$$$, then the cost of the array will be the maximum of the sum of the blocked elements ($$$4 + 3 = 7$$$) and the sums of the subarrays ($$$1$$$, $$$5 + 3 = 8$$$, $$$2$$$), which is $$$\max(7,1,8,2) = 8$$$. You need to output the minimum cost of the array after blocking.

Input: The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 30\,000$$$) — the number of queries.Each test case consists of two lines. The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the length of the array $$$a$$$. The second line contains $$$n$$$ elements $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the array $$$a$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case, output a single number — the minimum cost of blocking the array.

Note: The first test case matches with the array from the statement. To obtain a cost of $$$7$$$, you need to block the elements at positions $$$2$$$ and $$$4$$$. In this case, the cost of the array is calculated as the maximum of:  the sum of the blocked elements, which is $$$a_2 + a_4 = 7$$$.  the maximum sum of the segments into which the array is divided when the blocked elements are removed, i.e., the maximum of $$$a_1$$$, $$$a_3$$$, $$$a_5 + a_6 = \max(1,5,5) = 5$$$. So the cost is $$$\max(7,5) = 7$$$. In the second test case, you can block the elements at positions $$$1$$$ and $$$4$$$.In the third test case, to obtain the answer $$$11$$$, you can block the elements at positions $$$2$$$ and $$$5$$$. There are other ways to get this answer, for example, blocking positions $$$4$$$ and $$$6$$$.

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

Sample Outputs:
7
5
11

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
MOD = 1000000007
input = sys.stdin.readline
from collections import deque

def check(a, mid, s):
    n = len(a) - 1
    d = deque()
    dp = [0 for i in range(n + 2)]
    for i in range(n + 1):
        while len(d) > 0 and dp[d[-1]] >= dp[i]:
            d.pop()
        d.append(i)
        while s[i] - s[d[0]] > mid:
            d.popleft()
        dp[i + 1] = dp[d[0]] + a[i]
    return dp[n + 1] <= mid

def solve():
    n = int(input())
    a = list(map(int, input().split())) + [0]
    s = [0 for i in range(n + 2)]
    for i in range(n + 1):
        s[i + 1] = s[i] + a[i]
    l = 1
    r = sum(a)
    ans = r
    while l <= r:
        mid = (l + r) // 2
        if check(a, mid, s):
            ans = mid
            r = mid - 1
        else:
            l = mid + 1
    print(ans)
t = int(input())
for _ in range(t):
    solve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
MOD = 1000000007
input = sys.stdin.readline
from collections import deque
dp = [0]

def check(a, mid, s):
    global dp
    n = len(a) - 1
    d = deque()
    dp[0] = 0
    for i in range(n + 1):
        while len(d) > 0 and dp[d[-1]] >= dp[i]:
            d.pop()
        d.append(i)
        while s[i] - s[d[0]] > mid:
            d.popleft()
        dp[i + 1] = dp[d[0]] + a[i]
    return dp[n + 1] <= mid

def solve():
    global dp
    n = int(input())
    a = list(map(int, input().split())) + [0]
    s = [0 for i in range(n + 2)]
    for i in range(n + 1):
        s[i + 1] = s[i] + a[i]
    dp = [0 for i in range(n + 3)]
    l = 1
    r = sum(a)
    ans = r
    while l <= r:
        mid = (l + r) // 2
        if check(a, mid, s):
            ans = mid
            r = mid - 1
        else:
            l = mid + 1
    print(ans)
t = int(input())
for _ in range(t):
    solve()

Solution (Python):
import sys
from collections import deque

def rl():
    return list(map(int, input().split()))

def ri():
    return int(input())

def rs():
    return sys.stdin.readline().rstrip('\r\n')

def rm():
    return map(int, input().split())

def debug(v):
    print(f'value is {v}')
    return

def swap(i, j, arr):
    (arr[i], arr[j]) = (arr[j], arr[i])
    return

def check(x, a, n):
    dp = [float('inf')] * (n + 2)
    prefsum = [0] * (n + 3)
    for i in range(1, n + 3):
        prefsum[i] = a[i - 1] + prefsum[i - 1]
    q = deque()
    dp[0] = a[0]
    for i in range(n + 2):
        while q and prefsum[i] - prefsum[q[0] + 1] > x:
            q.popleft()
        dp[i] = a[i] + dp[q[0]] if q else a[i]
        while q and dp[q[-1]] >= dp[i]:
            q.pop()
        q.append(i)
    return dp[-1] <= x

def solve():
    n = ri()
    a = rl()
    a.append(0)
    a.insert(0, 0)
    (l, r) = (1, sum(a))
    lst = -1
    check(11, a, n)
    while l <= r:
        m = (r + l) // 2
        if check(m, a, n):
            lst = m
            r = m - 1
        else:
            l = m + 1
    print(lst)
if __name__ == '__main__':
    t = ri()
    while t:
        solve()
        t -= 1