Array Decrements (Codeforces 1690B)
Tags: Greedy, implementation

Kristina has two arrays $$$a$$$ and $$$b$$$, each containing $$$n$$$ non-negative integers. She can perform the following operation on array $$$a$$$ any number of times:   apply a decrement to each non-zero element of the array, that is, replace the value of each element $$$a_i$$$ such that $$$a_i > 0$$$ with the value $$$a_i - 1$$$ ($$$1 \le i \le n$$$). If $$$a_i$$$ was $$$0$$$, its value does not change. Determine whether Kristina can get an array $$$b$$$ from an array $$$a$$$ in some number of operations (probably zero). In other words, can she make $$$a_i = b_i$$$ after some number of operations for each $$$1 \le i \le n$$$?For example, let $$$n = 4$$$, $$$a = [3, 5, 4, 1]$$$ and $$$b = [1, 3, 2, 0]$$$. In this case, she can apply the operation twice:   after the first application of the operation she gets $$$a = [2, 4, 3, 0]$$$;  after the second use of the operation she gets $$$a = [1, 3, 2, 0]$$$. Thus, in two operations, she can get an array $$$b$$$ from an array $$$a$$$.

Input: The first line of the input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) —the number of test cases in the test.The descriptions of the test cases follow.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^4$$$).The second line of each test case contains exactly $$$n$$$ non-negative integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$).The third line of each test case contains exactly $$$n$$$ non-negative integers $$$b_1, b_2, \dots, b_n$$$ ($$$0 \le b_i \le 10^9$$$).It is guaranteed that the sum of $$$n$$$ values over all test cases in the test does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output on a separate line:  YES, if by doing some number of operations it is possible to get an array $$$b$$$ from an array $$$a$$$;  NO otherwise. You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as a positive response).

Note: The first test case is analyzed in the statement.In the second test case, it is enough to apply the operation to array $$$a$$$ once.In the third test case, it is impossible to get array $$$b$$$ from array $$$a$$$.

Sample Inputs:
6
4
3 5 4 1
1 3 2 0
3
1 2 1
0 1 0
4
5 3 7 2
1 1 1 1
5
1 2 3 4 5
1 2 3 4 6
1
8
0
1
4
6

Sample Outputs:
YES
YES
NO
NO
YES
NO

Solution (Python):
t = int(input().strip())
for i in range(t):
    f = 0
    n = int(input().strip())
    arr1 = list(map(int, input().split()))
    arr2 = list(map(int, input().split()))
    for i in range(n):
        if arr2[i] > arr1[i]:
            print('NO')
            f = 1
            break
    if f == 1:
        continue
    j = arr1.index(max(arr1))
    diff = arr1[j] - arr2[j]
    arr1 = [x - diff if x - diff >= 0 else 0 for x in arr1]
    if arr1 == arr2:
        print('YES')
    else:
        print('NO')

Solution (Python):
class Solution:

    def __init__(self):
        pass

    def solve(self):
        t = int(input())
        result = []
        for i in range(t):
            n = int(input())
            a = list(map(int, input().split()))
            b = list(map(int, input().split()))
            diff = []
            flag = True
            for (x, y) in zip(a, b):
                diff.append(x - y)
                if x - y < 0:
                    flag = False
                    break
            if not flag:
                result.append('NO')
                continue
            max_diff = max(diff)
            for (num, d) in enumerate(a):
                temp = a[num] - max_diff
                if temp < 0:
                    a[num] = 0
                else:
                    a[num] = temp
            for (x, y) in zip(a, b):
                if x != y:
                    flag = False
                    break
            if flag:
                result.append('YES')
            else:
                result.append('NO')
        for x in result:
            print(x)
if __name__ == '__main__':
    sol = Solution()
    sol.solve()

Solution (Python):
import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    (c, d) = (0, 0)
    for i in range(n):
        if b[i] != 0:
            c = a[i] - b[i]
            d = 1
            break
    if c < 0:
        print('NO')
    elif d == 0:
        print('YES')
    else:
        for i in range(n):
            if a[i] - b[i] == c or (b[i] == 0 and a[i] - b[i] <= c):
                continue
            else:
                print('NO')
                break
        else:
            print('YES')