[Solution] Yet Another Minimization Problem solution codeforces

Yet Another Minimization Problem solution codeforces – 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𝑖𝑛1≤i≤n) and swap 𝑎𝑖ai and 𝑏𝑖bi.

Let’s define the cost of the array 𝑎a as 𝑛𝑖=1𝑛𝑗=𝑖+1(𝑎𝑖+𝑎𝑗)2∑i=1n∑j=i+1n(ai+aj)2. Similarly, the cost of the array 𝑏b is 𝑛𝑖=1𝑛𝑗=𝑖+1(𝑏𝑖+𝑏𝑗)2∑i=1n∑j=i+1n(bi+bj)2.

Your task is to minimize the total cost of two arrays.

Yet Another Minimization Problem solution codeforces

Each test case consists of several test cases. The first line contains a single integer 𝑡t (1𝑡401≤t≤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𝑛1001≤n≤100) — the length of both arrays.

The second line of each test case contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖1001≤ai≤100) — elements of the first array.

The third line of each test case contains 𝑛n integers 𝑏1,𝑏2,,𝑏𝑛b1,b2,…,bn (1𝑏𝑖1001≤bi≤100) — elements of the second array.

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 100100.

Output

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

Yet Another Minimization Problem solution codeforces

3
1
3
6
4
3 6 6 6
2 7 4 1
4
6 7 2 4
2 5 3 5
output

Copy
0
987
914

Yet Another Minimization Problem solution codeforces Note

In the second test case, in one of the optimal answers after all operations 𝑎=[2,6,4,6]a=[2,6,4,6]𝑏=[3,7,6,1]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(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(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=987508+479=987.

Leave a Comment