Array Game (Codeforces 1904C)
Tags: Others, two pointers

You are given an array $$$a$$$ of $$$n$$$ positive integers. In one operation, you must pick some $$$(i, j)$$$ such that $$$1\leq i < j\leq |a|$$$ and append $$$|a_i - a_j|$$$ to the end of the $$$a$$$ (i.e. increase $$$n$$$ by $$$1$$$ and set $$$a_n$$$ to $$$|a_i - a_j|$$$). Your task is to minimize and print the minimum value of $$$a$$$ after performing $$$k$$$ operations.

Input: Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2\le n\le 2\cdot 10^3$$$, $$$1\le k\le 10^9$$$) — the length of the array and the number of operations you should perform.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le 10^{18}$$$) — the elements of the array $$$a$$$.It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$4\cdot 10^6$$$.

Output: For each test case, print a single integer — the smallest possible value of the minimum of array $$$a$$$ after performing $$$k$$$ operations.

Note: In the first test case, after any $$$k=2$$$ operations, the minimum value of $$$a$$$ will be $$$1$$$.In the second test case, an optimal strategy is to first pick $$$i=1, j=2$$$ and append $$$|a_1 - a_2| = 3$$$ to the end of $$$a$$$, creating $$$a=[7, 4, 15, 12, 3]$$$. Then, pick $$$i=3, j=4$$$ and append $$$|a_3 - a_4| = 3$$$ to the end of $$$a$$$, creating $$$a=[7, 4, 15, 12, 3, 3]$$$. In the final operation, pick $$$i=5, j=6$$$ and append $$$|a_5 - a_6| = 0$$$ to the end of $$$a$$$. Then the minimum value of $$$a$$$ will be $$$0$$$.In the third test case, an optimal strategy is to first pick $$$i=2, j=3$$$ to append $$$|a_2 - a_3| = 3$$$ to the end of $$$a$$$. Any second operation will still not make the minimum value of $$$a$$$ be less than $$$3$$$.

Sample Inputs:
4
5 2
3 9 7 15 1
4 3
7 4 15 12
6 2
42 47 50 54 62 79
2 1
500000000000000000 1000000000000000000

Sample Outputs:
1
0
3
500000000000000000

Solution (Python):
from bisect import bisect_right
test_cases = int(input())
for _ in range(test_cases):
    (n, k) = map(int, input().split())
    elements = list(map(int, input().split()))
    if k >= 3:
        print(0)
        continue
    elements.sort()
    min_difference = elements[0]
    for i in range(1, n):
        min_difference = min(min_difference, elements[i] - elements[i - 1])
    if k > 1:
        pairwise_differences = sorted([elements[j] - elements[i] for i in range(n) for j in range(i + 1, n)])
        for element in elements:
            index = bisect_right(pairwise_differences, element)
            if index < len(pairwise_differences):
                min_difference = min(min_difference, pairwise_differences[index] - element)
            if index - 1 >= 0:
                min_difference = min(min_difference, element - pairwise_differences[index - 1])
    print(min_difference)

Solution (Python):
from bisect import bisect_right
t = int(input())
for _ in range(t):
    (n, k) = [int(x) for x in input().split()]
    arr = [int(x) for x in input().split()]
    if k >= 3:
        print(0)
        continue
    arr.sort()
    ans = arr[0]
    for i in range(1, n):
        ans = min(ans, arr[i] - arr[i - 1])
    if k > 1:
        newarr = sorted([arr[j] - arr[i] for i in range(n) for j in range(i + 1, n)])
        for a in arr:
            idx = bisect_right(newarr, a)
            if idx < len(newarr):
                ans = min(ans, newarr[idx] - a)
            if idx - 1 >= 0:
                ans = min(ans, a - newarr[idx - 1])
    print(ans)

Solution (Python):
from bisect import bisect_right
t = int(input())
for _ in range(t):
    (n, k) = [int(x) for x in input().split()]
    arr = [int(x) for x in input().split()]
    if k >= 3:
        print(0)
        continue
    arr.sort()
    ans = arr[0]
    for i in range(1, n):
        ans = min(ans, arr[i] - arr[i - 1])
    if k > 1:
        newarr = sorted([arr[j] - arr[i] for i in range(n) for j in range(i + 1, n)])
        for a in arr:
            idx = bisect_right(newarr, a)
            if idx < len(newarr):
                ans = min(ans, newarr[idx] - a)
            if idx - 1 >= 0:
                ans = min(ans, a - newarr[idx - 1])
    print(ans)