Min-Max Array Transformation (Codeforces 1721C)
Tags: Greedy, two pointers

You are given an array $$$a_1, a_2, \dots, a_n$$$, which is sorted in non-descending order. You decided to perform the following steps to create array $$$b_1, b_2, \dots, b_n$$$:   Create an array $$$d$$$ consisting of $$$n$$$ arbitrary non-negative integers.  Set $$$b_i = a_i + d_i$$$ for each $$$b_i$$$.  Sort the array $$$b$$$ in non-descending order. You are given the resulting array $$$b$$$. For each index $$$i$$$, calculate what is the minimum and maximum possible value of $$$d_i$$$ you can choose in order to get the given array $$$b$$$.Note that the minimum (maximum) $$$d_i$$$-s are independent of each other, i. e. they can be obtained from different possible arrays $$$d$$$.

Input: The first line contains the single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of arrays $$$a$$$, $$$b$$$ and $$$d$$$.The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$; $$$a_i \le a_{i+1}$$$) — the array $$$a$$$ in non-descending order.The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^9$$$; $$$b_i \le b_{i+1}$$$) — the array $$$b$$$ in non-descending order.Additional constraints on the input:   there is at least one way to obtain the array $$$b$$$ from the $$$a$$$ by choosing an array $$$d$$$ consisting of non-negative integers;  the sum of $$$n$$$ doesn't exceed $$$2 \cdot 10^5$$$. 

Output: For each test case, print two lines. In the first line, print $$$n$$$ integers $$$d_1^{min}, d_2^{min}, \dots, d_n^{min}$$$, where $$$d_i^{min}$$$ is the minimum possible value you can add to $$$a_i$$$.Secondly, print $$$n$$$ integers $$$d_1^{max}, d_2^{max}, \dots, d_n^{max}$$$, where $$$d_i^{max}$$$ is the maximum possible value you can add to $$$a_i$$$.All $$$d_i^{min}$$$ and $$$d_i^{max}$$$ values are independent of each other. In other words, for each $$$i$$$, $$$d_i^{min}$$$ is just the minimum value among all possible values of $$$d_i$$$.

Note: In the first test case, in order to get $$$d_1^{min} = 5$$$, we can choose, for example, $$$d = [5, 10, 6]$$$. Then $$$b$$$ $$$=$$$ $$$[2+5,3+10,5+6]$$$ $$$=$$$ $$$[7,13,11]$$$ $$$=$$$ $$$[7,11,13]$$$.For $$$d_2^{min} = 4$$$, we can choose $$$d$$$ $$$=$$$ $$$[9, 4, 8]$$$. Then $$$b$$$ $$$=$$$ $$$[2+9,3+4,5+8]$$$ $$$=$$$ $$$[11,7,13]$$$ $$$=$$$ $$$[7,11,13]$$$.

Sample Inputs:
4
3
2 3 5
7 11 13
1
1000
5000
4
1 2 3 4
1 2 3 4
4
10 20 30 40
22 33 33 55

Sample Outputs:
5 4 2
11 10 8
4000
4000
0 0 0 0
0 0 0 0
12 2 3 15
23 13 3 15

Solution (Python):
import math
from collections import deque

def fastprime(n):
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return 0
    return 1

def power(n, a):
    res = 1
    while n:
        if n % 2:
            res *= n
            a -= 1
        else:
            n *= n
            a //= 2
    return res

def modpowe(n, a, p):
    res = 1
    while a:
        if a % 2:
            res = res * n % p
            a -= 1
        else:
            n = n * n % p
            a //= 2
    return res

def check(x):
    if x:
        print('YES')
    else:
        print('NO')

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    dmin = [0] * n
    dmax = [0] * n
    bptr = n - 1
    d = deque()
    for i in range(n - 1, -1, -1):
        while bptr >= 0 and b[bptr] >= a[i]:
            d.append(b[bptr])
            bptr -= 1
        mini = d[-1] - a[i]
        maxi = d[0] - a[i]
        dmin[i] = mini
        dmax[i] = maxi
        ct1 = n - i
        ct2 = n - bptr - 1
        if ct1 == ct2:
            d.clear()
    print(' '.join(map(str, dmin)))
    print(' '.join(map(str, dmax)))

def main():
    t = int(input())
    while t:
        solve()
        t -= 1
if __name__ == '__main__':
    main()

Solution (Python):
import sys
import bisect

def solve():
    inp = sys.stdin.readline
    bs = bisect.bisect
    n = int(inp())
    a = list(map(int, inp().split()))
    b = list(map(int, inp().split()))
    c = [0]
    for i in range(1, n):
        if b[i - 1] < a[i]:
            c.append(i)
    c.append(n)
    print(' '.join((str(b[bs(b, a[i] - 1)] - a[i]) for i in range(n))))
    print(' '.join((str(b[c[bs(c, i)] - 1] - a[i]) for i in range(n))))

def main():
    for i in range(int(sys.stdin.readline())):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
for k in range(int(input())):
    n = int(input())
    arr1 = list(map(int, input().split()))
    arr2 = list(map(int, input().split()))
    i = 0
    for x in arr1:
        while arr2[i] < x:
            i += 1
        print(arr2[i] - x, end=' ')
    print()
    temp = [0] * n
    j = n - 1
    temp[-1] = arr2[-1] - arr1[-1]
    for i in range(n - 2, -1, -1):
        if arr2[i] < arr1[i + 1]:
            j = i
        temp[i] = arr2[j] - arr1[i]
    print(' '.join(map(str, temp)))