Network Coverage (Codeforces 1373F)
Tags: Greedy, binary search

The government of Berland decided to improve network coverage in his country. Berland has a unique structure: the capital in the center and $$$n$$$ cities in a circle around the capital. The capital already has a good network coverage (so the government ignores it), but the $$$i$$$-th city contains $$$a_i$$$ households that require a connection.The government designed a plan to build $$$n$$$ network stations between all pairs of neighboring cities which will maintain connections only for these cities. In other words, the $$$i$$$-th network station will provide service only for the $$$i$$$-th and the $$$(i + 1)$$$-th city (the $$$n$$$-th station is connected to the $$$n$$$-th and the $$$1$$$-st city).All network stations have capacities: the $$$i$$$-th station can provide the connection to at most $$$b_i$$$ households.Now the government asks you to check can the designed stations meet the needs of all cities or not — that is, is it possible to assign each household a network station so that each network station $$$i$$$ provides the connection to at most $$$b_i$$$ households.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The first line of each test case contains the single integer $$$n$$$ ($$$2 \le n \le 10^6$$$) — the number of cities and stations.The second line of each test case contains $$$n$$$ integers ($$$1 \le a_i \le 10^9$$$) — the number of households in the $$$i$$$-th city.The third line of each test case contains $$$n$$$ integers ($$$1 \le b_i \le 10^9$$$) — the capacities of the designed stations.It's guaranteed that the sum of $$$n$$$ over test cases doesn't exceed $$$10^6$$$.

Output: For each test case, print YES, if the designed stations can meet the needs of all cities, or NO otherwise (case insensitive).

Note: In the first test case:   the first network station can provide $$$2$$$ connections to the first city and $$$1$$$ connection to the second city;  the second station can provide $$$2$$$ connections to the second city and $$$1$$$ connection to the third city;  the third station can provide $$$3$$$ connections to the third city. In the second test case:   the $$$1$$$-st station can provide $$$2$$$ connections to the $$$1$$$-st city;  the $$$2$$$-nd station can provide $$$3$$$ connections to the $$$2$$$-nd city;  the $$$3$$$-rd station can provide $$$3$$$ connections to the $$$3$$$-rd city and $$$1$$$ connection to the $$$1$$$-st station. In the third test case, the fourth city needs $$$5$$$ connections, but the third and the fourth station has $$$4$$$ connections in total.

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

Sample Outputs:
YES
YES
NO
YES
YES

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def test(A, B, x):
    """"""
    n = len(A)
    start = A[0] - x
    yi = x
    for i in range(1, n):
        x2 = min(B[i - 1] - yi, A[i])
        y2 = A[i] - x2
        if y2 > B[i]:
            return 1
        yi = y2
    if start + yi <= B[n - 1]:
        return 0
    else:
        return 2

def process(A, B):
    n = len(A)
    for i in range(n):
        if A[i] > B[i] + B[(i - 1) % n]:
            sys.stdout.write('NO\n')
            return
    if sum(A) > sum(B):
        sys.stdout.write('NO\n')
        return
    ''
    l = max(A[0] - B[-1], 0)
    r = min(A[0], B[0])
    if test(A, B, l) == 0 or test(A, B, r) == 0:
        sys.stdout.write('YES\n')
        return
    else:
        while l + 1 < r:
            m = (l + r) // 2
            t1 = test(A, B, m)
            if t1 == 0:
                sys.stdout.write('YES\n')
                return
            elif t1 == 2:
                (l, r) = (m, r)
            else:
                (l, r) = (l, m)
        sys.stdout.write('NO\n')
        return
t = int(input())
for i in range(t):
    n = int(input())
    A = [int(x) for x in input().split()]
    B = [int(x) for x in input().split()]
    process(A, B)

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def test(A, B, x):
    """"""
    n = len(A)
    start = A[0] - x
    yi = x
    for i in range(1, n):
        yi = A[i] - min(B[i - 1] - yi, A[i])
        if yi > B[i]:
            return 1
    if start + yi <= B[n - 1]:
        return 0
    else:
        return 2

def process(A, B):
    n = len(A)
    for i in range(n):
        if A[i] > B[i] + B[(i - 1) % n]:
            sys.stdout.write('NO\n')
            return
    if sum(A) > sum(B):
        sys.stdout.write('NO\n')
        return
    ''
    l = max(A[0] - B[-1], 0)
    r = min(A[0], B[0])
    if test(A, B, l) == 0 or test(A, B, r) == 0:
        sys.stdout.write('YES\n')
        return
    else:
        while l + 1 < r:
            m = (l + r) // 2
            t1 = test(A, B, m)
            if t1 == 0:
                sys.stdout.write('YES\n')
                return
            elif t1 == 2:
                (l, r) = (m, r)
            else:
                (l, r) = (l, m)
        sys.stdout.write('NO\n')
        return
t = int(input())
for i in range(t):
    n = int(input())
    A = [int(x) for x in input().split()]
    B = [int(x) for x in input().split()]
    process(A, B)

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')

def RL():
    return map(int, sys.stdin.readline().rstrip().split())

def RLL():
    return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
    return int(input())

def comb(n, m):
    return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
    return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
    return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')
from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def main():
    for _ in range(N()):
        n = N()
        arra = RLL()
        arrb = RLL()
        (l, r) = (0, min(arra[0], arrb[0]))

        def c(num):
            dif = arrb[0] - num
            hv = dif
            for i in range(1, n):
                now = arra[i] - hv
                if arrb[i] < now and now >= 0:
                    return (0, 1)
                if now >= 0:
                    hv = arrb[i] - now
                else:
                    hv = arrb[i]
            return (1, 1) if num + hv >= arra[0] else (0, 0)
        res = False
        while l <= r:
            m = (l + r) // 2
            (st, tg) = c(m)
            if st:
                res = True
                break
            if tg:
                r = m - 1
            else:
                l = m + 1
        print('YES' if res else 'NO')
if __name__ == '__main__':
    main()