Pchelyonok and Segments (Codeforces 1582E)
Tags: Math, binary search

Pchelyonok decided to give Mila a gift. Pchelenok has already bought an array $$$a$$$ of length $$$n$$$, but gifting an array is too common. Instead of that, he decided to gift Mila the segments of that array!Pchelyonok wants his gift to be beautiful, so he decided to choose $$$k$$$ non-overlapping segments of the array $$$[l_1,r_1]$$$, $$$[l_2,r_2]$$$, $$$\ldots$$$ $$$[l_k,r_k]$$$ such that:  the length of the first segment $$$[l_1,r_1]$$$ is $$$k$$$, the length of the second segment $$$[l_2,r_2]$$$ is $$$k-1$$$, $$$\ldots$$$, the length of the $$$k$$$-th segment $$$[l_k,r_k]$$$ is $$$1$$$  for each $$$i<j$$$, the $$$i$$$-th segment occurs in the array earlier than the $$$j$$$-th (i.e. $$$r_i<l_j$$$)  the sums in these segments are strictly increasing (i.e. let $$$sum(l \ldots r) = \sum\limits_{i=l}^{r} a_i$$$ — the sum of numbers in the segment $$$[l,r]$$$ of the array, then $$$sum(l_1 \ldots r_1) < sum(l_2 \ldots r_2) < \ldots < sum(l_k \ldots r_k)$$$). Pchelenok also wants his gift to be as beautiful as possible, so he asks you to find the maximal value of $$$k$$$ such that he can give Mila a gift!

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The next $$$2 \cdot t$$$ lines contain the descriptions of test cases. The description of each test case consists of two lines.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the array.The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of 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, print the maximum possible value of $$$k$$$.


Sample Inputs:
5
1
1
3
1 2 3
5
1 1 2 2 3
7
1 2 1 1 3 2 6
5
9 6 7 9 7

Sample Outputs:
1
1
2
3
1

Solution (Python):
""""""
import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
output = sys.stdout.write
from math import sqrt

def solve(N, nums):
    K = int(sqrt(N * 2)) + 1
    dp = [0] * N
    mx = -float('inf')
    for i in range(N - 1, -1, -1):
        mx = max(mx, nums[i])
        dp[i] = mx
    res = 1
    for k in range(2, K):
        ndp = [0] * N
        offset = k * (k + 1) // 2
        mx = 0
        s = sum(nums[N - offset:N - offset + k])
        for i in range(N - offset, -1, -1):
            if i < N - offset:
                s += nums[i] - nums[i + k]
            if s < dp[i + k]:
                mx = max(mx, s)
            ndp[i] = mx
        dp = ndp
        if dp[0] > 0:
            res = k
    return res

def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        nums = list(map(int, input().split()))
        out = solve(N, nums)
        output(str(out) + '\n')
if __name__ == '__main__':
    main()

Solution (Python):
""""""
import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
output = sys.stdout.write
from math import sqrt
DEBUG = 0

def solve(N, nums):
    K = int(sqrt(N * 2)) + 1
    if DEBUG:
        print(' '.join(map(str, list(range(N)))))
        print(' '.join(map(str, nums)))
    dp = [0] * N
    mx = -float('inf')
    for i in range(N - 1, -1, -1):
        mx = max(mx, nums[i])
        dp[i] = mx
    if DEBUG:
        print(f'\ndp[i][1] = {[dp[i][1] for i in range(N)]}')
    res = 1
    for k in range(2, K):
        ndp = [0] * N
        offset = k * (k + 1) // 2
        mx = 0
        s = sum(nums[N - offset:N - offset + k])
        if DEBUG:
            print(f'\ntrying k={k}: starting s={s}')
        for i in range(N - offset, -1, -1):
            if i < N - offset:
                s += nums[i] - nums[i + k]
            mx2 = dp[i + k]
            if s < mx2:
                mx = max(mx, s)
            ndp[i] = mx
            if DEBUG:
                print(f'k={k}, i={i}: s={s}, mx={mx}, mx2={mx2}, dp[{i}][{k}]={dp[i][k]}')
        dp = ndp
        if dp[0] > 0:
            res = k
    if DEBUG:
        print(f'\ndp[0]={dp}')
    return res

def test():

    def brute(N, nums):

        def _brute(i, k, bound):
            nonlocal N, nums
            if i + k * (k + 1) // 2 > N:
                return False
            if k == 0:
                return True
            for j in range(i, N - k):
                s = sum(nums[j:j + k])
                if s <= bound:
                    continue
                if _brute(j + k, k - 1, s):
                    print(f'_brute found for i={i} k={k}: j+k={j + k}, s={s}')
                    return True
            return False
        K = int(sqrt(N * 2)) + 2
        for k in range(K, 0, -1):
            if k * (k + 1) // 2 > N:
                continue
            for i in range(N):
                if _brute(i, k, -float('inf')):
                    print(f'brute found: i={i}, k={k}')
                    return k
    import random
    random.seed(123)
    for _ in range(10):
        N = random.randint(3, 6)
        nums = [random.randint(1, 10) for _ in range(N)]
        res_brute = brute(N, nums)
        res_solve = solve(N, nums)
        assert res_brute == res_solve, f'Got brute={res_brute}, solve={res_solve}: N={N}, nums={nums}'
    print('tests passed')

def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        nums = list(map(int, input().split()))
        out = solve(N, nums)
        output(str(out) + '\n')
if __name__ == '__main__':
    main()

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
inf = float('inf')
dp = [[0.0] * 450 for _ in range(10 ** 5 + 10)]

def solve():
    n = int(input())
    a = list(map(float, input().split()))
    pref = a[:]
    for i in range(1, n):
        pref[i] += pref[i - 1]
    k = 0
    while k * (k + 1) // 2 <= n:
        k += 1

    def f(l, r):
        return pref[r] - (pref[l - 1] if l >= 1 else 0)
    for j in range(k):
        dp[n][j] = -inf
    dp[n][0] = inf
    for i in range(n - 1, -1, -1):
        for j in range(k):
            dp[i][j] = dp[i + 1][j]
            if j and i + j - 1 <= n - 1 and (f(i, i + j - 1) < dp[i + j][j - 1]):
                dp[i][j] = max(dp[i][j], f(i, i + j - 1))
    ans = 0
    for j in range(k):
        if dp[0][j] > 0:
            ans = j
    print(ans)
for nt in range(int(input())):
    solve()