Yet Another Minimization Problem (Codeforces 1637D)
Tags: Greedy, dp

You are given two arrays $$$a$$$ and $$$b$$$, both of length $$$n$$$.You can perform the following operation any number of times (possibly zero): select an index $$$i$$$ ($$$1 \leq i \leq n$$$) and swap $$$a_i$$$ and $$$b_i$$$.Let's define the cost of the array $$$a$$$ as $$$\sum_{i=1}^{n} \sum_{j=i + 1}^{n} (a_i + a_j)^2$$$. Similarly, the cost of the array $$$b$$$ is $$$\sum_{i=1}^{n} \sum_{j=i + 1}^{n} (b_i + b_j)^2$$$.Your task is to minimize the total cost of two arrays.

Input: Each test case consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 40$$$) — the number of test cases. The following is a description of the input data sets.The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 100$$$) — the length of both arrays.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 100$$$) — elements of the first array.The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq 100$$$) — elements of the second array.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$100$$$.

Output: For each test case, print the minimum possible total cost.

Note: In the second test case, in one of the optimal answers after all operations $$$a = [2, 6, 4, 6]$$$, $$$b = [3, 7, 6, 1]$$$.The cost of the array $$$a$$$ equals to $$$(2 + 6)^2 + (2 + 4)^2 + (2 + 6)^2 + (6 + 4)^2 + (6 + 6)^2 + (4 + 6)^2 = 508$$$.The cost of the array $$$b$$$ equals to $$$(3 + 7)^2 + (3 + 6)^2 + (3 + 1)^2 + (7 + 6)^2 + (7 + 1)^2 + (6 + 1)^2 = 479$$$.The total cost of two arrays equals to $$$508 + 479 = 987$$$.

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

Sample Outputs:
0
987
914

Solution (Python):
def cal():
    n = int(input())
    a = (int(i) for i in input().split())
    b = (int(i) for i in input().split())
    dp = 1
    ans = 0
    total = 0
    for (i, j) in zip(a, b):
        dp = dp << i | dp << j
        total += i + j
        ans += i * i + j * j
    i = total // 2
    dp >>= i
    while dp > 0 and i <= total:
        if dp & 1:
            return ans * (n - 2) + i * i + (total - i) ** 2
        dp >>= 1
        i += 1
if __name__ == '__main__':
    t = int(input())
    for i in range(t):
        print(cal())

Solution (Python):
t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    res = 0
    sum = 0
    if n >= 1:
        for i in range(n):
            res += (n - 2) * (a[i] * a[i] + b[i] * b[i])
            sum += a[i] + b[i]
    halfSum = sum / 2
    curValues = {0}
    for i in range(n):
        nextValues = set()
        for j in curValues:
            nextValues.add(j + a[i])
            nextValues.add(j + b[i])
        curValues = nextValues
    minValue = 0
    for i in curValues:
        if abs(halfSum - i) < abs(halfSum - minValue):
            minValue = i
    res += minValue * minValue + (sum - minValue) * (sum - minValue)
    print(res)

Solution (Python):
t = int(input())
while t > 0:
    t = t - 1
    n = int(input())
    a = input().split()
    b = input().split()
    for i in range(0, n):
        a[i] = int(a[i])
        b[i] = int(b[i])
    arr = {0}
    for i in range(n - 1, -1, -1):
        brr = set()
        for j in arr:
            brr.add(a[i] - b[i] + j)
            brr.add(b[i] - a[i] + j)
        arr = brr
    ans = []
    for i in arr:
        ans.append(abs(i))
    x = min(ans)
    ans = 0
    for i in a:
        ans = ans + i * i
    for i in b:
        ans = ans + i * i
    ans = (n - 2) * ans
    p = sum(a) + sum(b)
    ans = ans + (p * p + x * x) / 2
    print(int(ans))