Rudolf and Imbalance (Codeforces 1941F)
Tags: Greedy, two pointers

Rudolf has prepared a set of $$$n$$$ problems with complexities $$$a_1 < a_2 < a_3 < \dots < a_n$$$. He is not entirely satisfied with the balance, so he wants to add at most one problem to fix it.For this, Rudolf came up with $$$m$$$ models of problems and $$$k$$$ functions. The complexity of the $$$i$$$-th model is $$$d_i$$$, and the complexity of the $$$j$$$-th function is $$$f_j$$$. To create a problem, he selects values $$$i$$$ and $$$j$$$ ($$$1 \le i \le m$$$, $$$1 \le j \le k$$$) and by combining the $$$i$$$-th model with the $$$j$$$-th function, he obtains a new problem with complexity $$$d_i + f_j$$$ (a new element is inserted into the array $$$a$$$).To determine the imbalance of the set, Rudolf sorts the complexities of the problems in ascending order and finds the largest value of $$$a_i - a_{i - 1}$$$ ($$$i > 1$$$).What is the minimum value of imbalance that Rudolf can achieve by adding at most one problem, created according to the described rules?

Input: The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le m, k \le 2 \cdot 10^5$$$) — the number of prepared problems, the number of models, and the number of functions, respectively.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, a_3, \dots a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^9$$$, $$$a_i < a_{i+1}$$$) — the complexities of the prepared problems.The third line of each test case contains $$$m$$$ integers $$$d_1, d_2, d_3, \dots d_m$$$ ($$$1 \le d_i \le 10^9$$$) — the complexities of the models.The fourth line of each test case contains $$$k$$$ integers $$$f_1, f_2, f_3, \dots f_k$$$ ($$$1 \le f_i \le 10^9$$$) — the complexities of the functions.It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$10^5$$$.It is guaranteed that the sum of $$$m$$$ over all testcases does not exceed $$$2 \cdot 10^5$$$.It is guaranteed that the sum of $$$k$$$ over all testcases does not exceed $$$2 \cdot 10^5$$$.

Output: For each testcase, output a single number — the minimum imbalance that Rudolf can achieve.


Sample Inputs:
7
5 5 5
5 10 15 20 26
11 14 16 13 8
16 4 5 3 1
7 6 5
1 4 7 10 18 21 22
2 3 5 7 4 2
6 8 9 3 2
7 6 5
1 4 7 10 18 21 22
2 3 5 7 4 2
6 8 13 3 2
5 6 3
2 10 13 20 25
11 6 10 16 14 5
6 17 15
4 2 2
11 12 14 15
19 14
10 6
8 4 2
3 10 16 18 21 22 29 30
9 13 16 15
4 2
2 4 7
4 21
4 15 14 5
20 1 15 1 12 5 11

Sample Outputs:
5
4
5
8
2
7
11

Solution (Python):
t = int(input())
for _ in range(t):
    (n, m, k) = map(int, input().split())
    problems = list(sorted(map(int, input().split())))
    models = list(sorted(map(int, input().split())))
    functions = list(sorted(map(int, input().split())))
    max_diff = [problems[0], problems[1]]
    for i in range(2, n):
        if problems[i] - problems[i - 1] > max_diff[1] - max_diff[0]:
            max_diff = [problems[i - 1], problems[i]]
    target = (max_diff[0] + max_diff[1]) // 2
    target2 = (max_diff[0] + max_diff[1] + 1) // 2

    def do(target):
        middle = models[0] + functions[0]
        min_diff = abs(models[0] + functions[0] - target)
        (i, j) = (0, len(functions) - 1)
        while i < len(models) and j >= 0:
            current_sum = models[i] + functions[j]
            current_diff = abs(current_sum - target)
            if current_diff < min_diff:
                min_diff = current_diff
                middle = current_sum
            if current_sum < target:
                i += 1
            elif current_sum > target:
                j -= 1
            else:
                break
        return middle
    middle1 = do(target)
    middle2 = do(target2)
    if max(abs(max_diff[0] - middle1), abs(max_diff[1] - middle1)) < max(abs(max_diff[0] - middle2), abs(max_diff[1] - middle2)):
        middle = middle1
    else:
        middle = middle2
    imbalance = max_diff[1] - max_diff[0]
    if max_diff[0] <= middle <= max_diff[1]:
        imbalance = max(abs(max_diff[0] - middle), abs(max_diff[1] - middle))
    new_diff = [55, 0]
    for i in range(1, n):
        if [problems[i - 1], problems[i]] == max_diff:
            continue
        if problems[i] - problems[i - 1] > new_diff[1] - new_diff[0]:
            new_diff = [problems[i - 1], problems[i]]
    print(max(imbalance, new_diff[1] - new_diff[0]))

Solution (Python):
I = lambda : list(map(int, input().split(' ')))
R = lambda : int(input())
import math
for kp in range(R()):
    (n, m, k) = I()
    a = I()
    d = I()
    f = I()
    d.sort(reverse=True)
    f.sort()
    n_val = 0
    max_val = 0
    max_ind = -1
    req = 0
    for i in range(1, n):
        temp = a[i] - a[i - 1]
        if temp > max_val:
            max_val = temp
            n_val = 0
            req = (a[i] + a[i - 1]) // 2
            max_ind = i
        if temp == max_val:
            n_val += 1
    if n_val > 1 or max_val == 0:
        print(max_val)
        continue
    else:
        ind1 = 0
        ind2 = 0
        min_g = max_val
        val = -1
        while ind1 < m or ind2 < k:
            new_val = d[ind1] + f[ind2]
            g = req - (d[ind1] + f[ind2])
            if new_val <= a[max_ind] and new_val >= a[max_ind - 1]:
                gap = max(new_val - a[max_ind - 1], -new_val + a[max_ind])
                if gap < min_g:
                    val = new_val
                    min_g = gap
            if g > 0:
                if ind2 >= k - 1:
                    break
                else:
                    ind2 += 1
            elif g < 0:
                if ind1 >= m - 1:
                    break
                else:
                    ind1 += 1
            elif g == 0:
                val = d[ind1] + f[ind2]
                break
        if val != -1:
            a.insert(max_ind, val)
        max_val_2 = 0
        for i in range(1, len(a)):
            max_val_2 = max(max_val_2, a[i] - a[i - 1])
        print(max_val_2)

Solution (Python):
def minimizeComplexity(arr, d, f):
    lol = float('inf')
    left = 0
    right = len(d + f) - 1
    toOptimize = diff(arr, [])
    toOptimizeele = max(toOptimize)
    valueToOptimize1 = arr[toOptimize.index(toOptimizeele)]
    valueToOptimize2 = arr[toOptimize.index(toOptimizeele) + 1]
    d.sort()
    f.sort()
    (left, right) = (0, len(f) - 1)
    while left < len(d) and right >= 0:
        if d[left] + f[right] < valueToOptimize2 and d[left] + f[right] > valueToOptimize1:
            lol = min(lol, max(valueToOptimize2 - (d[left] + f[right]), d[left] + f[right] - valueToOptimize1))
            if d[left] + f[right] - valueToOptimize1 < valueToOptimize2 - (d[left] + f[right]):
                left += 1
            else:
                right -= 1
        elif d[left] + f[right] <= valueToOptimize1:
            left += 1
        else:
            right -= 1
    if lol == float('inf'):
        return max(toOptimize)
    del toOptimize[toOptimize.index(max(toOptimize))]
    toOptimize.append(lol)
    return max(toOptimize)

def diff(arr, soln):
    for i in range(1, len(arr)):
        soln.append(arr[i] - arr[i - 1])
    return soln
t = int(input())
while t != 0:
    s = input()
    arr = input()
    arr = [int(x) for x in arr.split()]
    d = input()
    d = [int(x) for x in d.split()]
    f = input()
    f = [int(x) for x in f.split()]
    print(minimizeComplexity(arr, d, f))
    t -= 1