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.


-----Examples-----

Input
3
1
3
6
4
3 6 6 6
2 7 4 1
4
6 7 2 4
2 5 3 5
Output
0
987
914


-----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$.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Mathematics

Greedy algorithms
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
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
t = int(input())
for i in range(t):
	print(cal())


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)


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))


import sys
import io
import math
import collections
import decimal
import itertools
import bisect
import heapq

def input():
	return sys.stdin.readline()[:-1]
INF = 10 ** 10

def solve(N, A, B):
	s = sum(A) + sum(B)
	dp = [False] * (s + 1)
	dp[0] = True
	for i in range(N):
		for n in reversed(range(s + 1)):
			if dp[n]:
				if 0 <= n + A[i] <= s:
					dp[n + A[i]] |= True
				if 0 <= n + B[i] <= s:
					dp[n + B[i]] |= True
				dp[n] = False
	n_good = min(((abs(n - s / 2), n) for n in range(s + 1) if dp[n]))[1]
	ans = (N - 2) * sum((a ** 2 for a in A + B)) + n_good ** 2 + (s - n_good) ** 2
	return ans
T0 = int(input())
for _ in range(T0):
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	print(solve(N, A, B))


import sys
from collections import deque
input = sys.stdin.readline

def main():
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	if n == 1:
		return 0
	S = sum(A) + sum(B)
	ans = curr = 0
	ps = [0] * n
	for i in range(n):
		ans += A[i] ** 2 + B[i] ** 2
		curr += A[i] + B[i]
		ps[i] = curr
	ans *= n - 2
	q = deque([(A[0], 0)])
	vis = {(A[0], 0)}
	nums = [False] * 10001
	while q:
		(val, idx) = q.popleft()
		if idx == n - 1:
			nums[val] = True
			nums[ps[idx] - val] = True
			continue
		if (val + A[idx + 1], idx + 1) not in vis:
			vis.add((val + A[idx + 1], idx + 1))
			q.append((val + A[idx + 1], idx + 1))
		if (val + B[idx + 1], idx + 1) not in vis:
			vis.add((val + B[idx + 1], idx + 1))
			q.append((val + B[idx + 1], idx + 1))
	target = S // 2
	v = 0
	diff = float('inf')
	for i in range(10001):
		if nums[i] and abs(i - target) < diff:
			diff = abs(i - target)
			v = i
	ans += 2 * v * (v - S) + S ** 2
	return ans
for _ in range(int(input())):
	print(main())


import sys
input = sys.stdin.readline

def rec(n, a, b, z):
	dp = [[False for _ in range(z + 1)] for _ in range(n)]
	dp[0][a[0]] = True
	dp[0][b[0]] = True
	for i in range(1, n):
		for j in range(z + 1):
			p = j >= a[i] and dp[i - 1][j - a[i]]
			q = j >= b[i] and dp[i - 1][j - b[i]]
			dp[i][j] = p or q
	return dp[n - 1]

def solve(n, a, b):
	S = sum([max(a[i], b[i]) for i in range(n)])
	total = sum(a) + sum(b)
	check = rec(n, a, b, S)
	ans = 10 ** 9
	for j in range(S + 1):
		if check[j]:
			ans = min(ans, j * j + (total - j) * (total - j))
	v = (n - 2) * sum([a[i] * a[i] + b[i] * b[i] for i in range(n)])
	return v + ans
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	print(solve(n, a, b))


def memoize(function):
	cache = {}

	def decorated_function(*args):
		try:
			return cache[args]
		except KeyError:
			val = function(*args)
			cache[args] = val
			return val
	return decorated_function

def lookup(n, A, B):

	@memoize
	def go(i, sa):
		if i == n:
			return abs(2 * sa - S)
		return min(go(i + 1, sa + A[i]), go(i + 1, sa + B[i]))
	if n == 1:
		return 0
	S = sum(A) + sum(B)
	v = go(0, 0)
	sa = (v + S) // 2
	m = sa ** 2 + (S - sa) ** 2
	return (n - 2) * (sum((a ** 2 for a in A)) + sum((b ** 2 for b in B))) + m
T = int(input())
for _ in range(T):
	n = int(input())
	A = list(map(int, input().split(' ')))
	B = list(map(int, input().split(' ')))
	print(lookup(n, A, B))


n = int(input())
for e in range(n):
	t = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	a = 0
	for i in range(len(l1)):
		a += (len(l1) - 1) * l1[i] ** 2 + (len(l1) - 1) * l2[i] ** 2

	def dp(s1, s2, h, i):
		if i == -1:
			return 0
		if (s1, s2, i) in h:
			return h[s1, s2, i]
		h[s1, s2, i] = min(s1 * l1[i] + s2 * l2[i] + dp(s1 + l1[i], s2 + l2[i], h, i - 1), s1 * l2[i] + s2 * l1[i] + dp(s1 + l2[i], s2 + l1[i], h, i - 1))
		return h[s1, s2, i]
	h = {}
	q = len(l1) - 1
	s1 = 0
	s2 = 0
	a1 = 2 * dp(s1, s2, h, q)
	ans = a1 + a
	print(ans)


import sys
from math import *
from functools import *
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ans = (n - 2) * sum((a[i] ** 2 + b[i] ** 2 for i in range(n)))
	temp = sum((a[i] + b[i] for i in range(n)))
	summ = sum((max(a[i], b[i]) for i in range(n))) + 1
	dp = [[0 for s in range(summ)] for i in range(n)]
	for i in range(n):
		if i == 0:
			dp[i][a[i]] = 1
			dp[i][b[i]] = 1
			continue
		for s in range(summ):
			if s >= a[i] and s >= b[i]:
				dp[i][s] = dp[i - 1][s - a[i]] | dp[i - 1][s - b[i]]
			elif s >= a[i]:
				dp[i][s] = dp[i - 1][s - a[i]]
			elif s >= b[i]:
				dp[i][s] = dp[i - 1][s - b[i]]
	minn = 10 ** 9
	for s in range(summ):
		minn = min(minn, s * s + (temp - s) ** 2) if dp[n - 1][s] else minn
	print(ans + minn)