Ensure that you are logged in and have the required permissions to access the test.

Nearby Squares

3.5

12 votes
Recursion, Recursion and Backtracking, Basic Programming
Problem

You are given an array A of length N. There are two empty arrays, B and C. You have to put every element of A into either B or C.

The score of an array is defined as the square of the sum of all of its elements. Find the minimum possible absolute difference between the score of B and C.

Input Format:

  • The first line of input contains a single integer T, denoting the number of test cases.
  • The first line of each test case contains a single integer N, denoting the length of the array A.
  • The second line of each test case contains N integers, denoting the elements of array A.

Output Format:

For each test case, print the minimum possible absolute difference between the score of B and the score of C.

Constraints:

1<=T<=10

1<=N<=20

1<=A[i]<=108

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

First test case:
We can put the third element in B and the other elements in C.
The score of B is 102=100.
The score of C is (4+5+3)2=144.
Their absolute difference is |100144|=44.
It can be shown that this is the minimum possible absolute difference. Thus, the answer is 44.

Second test case:
We can put the first three elements in B and the last two elements in C.
The score of B is (1+3+5)2=81.
The score of C is (4+5)2=81.
Their absolute difference is |8181|=0. Thus, the answer is 0.

Editor Image

?