Missing Subarray Sum
Contest: Codeforces Round 941 (Div. 1)
Difficulty rating: 2900
Tags: constructive algorithms

There is a hidden array $$$a$$$ of $$$n$$$ positive integers. You know that $$$a$$$ is a palindrome, or in other words, for all $$$1 \le i \le n$$$, $$$a_i = a_{n + 1 - i}$$$. You are given the sums of all but one of its distinct subarrays, in arbitrary order. The subarray whose sum is not given can be any of the $$$\frac{n(n+1)}{2}$$$ distinct subarrays of $$$a$$$.

Recover any possible palindrome $$$a$$$. The input is chosen such that there is always at least one array $$$a$$$ that satisfies the conditions.

An array $$$b$$$ is a subarray of $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input format:
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 200$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 1000$$$) — the size of the array $$$a$$$.

The next line of each test case contains $$$\frac{n(n+1)}{2} - 1$$$ integers $$$s_i$$$ ($$$1\leq s_i \leq 10^9$$$) — all but one of the subarray sums of $$$a$$$.

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

Additional constraint on the input: There is always at least one valid solution.

Hacks are disabled for this problem.

Output format:
For each test case, print one line containing $$$n$$$ positive integers $$$a_1, a_2, \cdots a_n$$$ — any valid array $$$a$$$. Note that $$$a$$$ must be a palindrome.

If there are multiple solutions, print any.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
For the first example case, the subarrays of $$$a = [1, 2, 1]$$$ are:

- $$$[1]$$$ with sum $$$1$$$,
- $$$[2]$$$ with sum $$$2$$$,
- $$$[1]$$$ with sum $$$1$$$,
- $$$[1, 2]$$$ with sum $$$3$$$,
- $$$[2, 1]$$$ with sum $$$3$$$,
- $$$[1, 2, 1]$$$ with sum $$$4$$$.

For the second example case, the missing subarray sum is $$$4$$$, for the subarray $$$[2, 2]$$$.

For the third example case, the missing subarray sum is $$$13$$$, because there are two subarrays with sum $$$13$$$ ($$$[3, 5, 5]$$$ and $$$[5, 5, 3]$$$) but $$$13$$$ only occurs once in the input.

Example input:
7
3
1 2 3 4 1
4
18 2 11 9 7 11 7 2 9
4
5 10 5 16 3 3 13 8 8
4
8 10 4 6 4 20 14 14 6
5
1 2 3 4 5 4 3 2 1 1 2 3 2 1
5
1 1 2 2 2 3 3 3 3 4 5 5 6 8
3
500000000 1000000000 500000000 500000000 1000000000

Example output:
1 2 1 
7 2 2 7 
3 5 5 3 
6 4 4 6 
1 1 1 1 1 
2 1 2 1 2 
500000000 500000000 500000000

Editorial:
Let's first look at the set of subarray sums of a palindromic array $$$a$$$ of $$$n$$$ positive integers. Because $$$a$$$ is a palindrome, the sum of the subarray with indices in the range $$$[l, r]$$$ is the same as the sum of the subarray with indices in the range $$$[n + 1 - r, n + 1 - l]$$$. So if we ignore all subarrays where $$$l + r = n + 1$$$ (subarrays centered at the center of $$$a$$$), each sum must appear an even number of times.
Also, every "centered" subarray $$$[l, n + 1 - l]$$$ must have a unique sum. This is because all elements of $$$a$$$ are strictly positive, and if the "centered" subarrays are ordered by length, each one contains all elements in the previous one, along with two new elements, so its sum must be strictly greater.
Therefore, the set of subarray sums that appear an odd number of times is exactly the set of sums of subarrays centered at the center of $$$a$$$. For example, in the array $$$a = [1, 2, 3, 2, 1]$$$, the sums that appear an odd number of times are:
• $$$3$$$ ($$$[3]$$$, $$$[1, 2]$$$, $$$[2, 1]$$$)
• $$$7$$$ ($$$[2, 3, 2]$$$)
• $$$9$$$ ($$$[1, 2, 3, 2, 1]$$$)
So if we have all $$$\frac{n(n+1)}{2}$$$ subarray sums of $$$a$$$, we can then use the "centered" sums to reconstruct $$$a$$$ itself. The smallest "centered" sum is either the middle element or the sum of the middle two (equal) elements, depending on the parity of $$$n$$$, and for each "centered" sum in ascending order after that, its difference with the previous sum must be the sum of the next two (equal) elements closest to the center of $$$a$$$.
Now, let's find out how to reconstruct the missing sum. We consider two cases:
1. If the missing sum is for a "centered" subarray, then there will be exactly $$$\lceil\frac{n}{2}\rceil - 1$$$ sums that appear an odd number of times in the input. We can use these sums to construct a palindromic array $$$b$$$ of size $$$n-2$$$ as described above.We can then remove all sums of subarrays of $$$b$$$ from the initial input list, and look at what is remaining. If we let $$$[l, r]$$$ be the indices of the missing subarray, the largest remaining sum in the list must be the sum of $$$[1, r]$$$ in $$$a$$$ (or equivalently $$$[l, n]$$$). Let this sum be $$$x$$$ and the sum of $$$b$$$ be $$$y$$$.If $$$l > 1$$$ (and therefore $$$r < n$$$), the missing sum must be $$$2x-y$$$, because the $$$2x$$$ part includes everything in the missing subarray twice, and everything else once, and $$$y$$$ includes everything once. $$$l=1$$$, $$$r=n$$$ initially seems like it will be an edge case, but the same equation works there as well, since $$$2x$$$ includes everything in the missing array (all of $$$a$$$) once, and everything in $$$b$$$ once, and $$$y$$$ includes everything in $$$b$$$ once.
2. If the missing sum is not for a "centered" subarray, then there will be exactly $$$\lceil\frac{n}{2}\rceil + 1$$$ sums that appear an odd number of times in the input. We can use these sums to construct a palindromic array $$$b$$$ of size $$$n+2$$$ as described above.In a similar way to the previous case, we can then remove all sums from the initial input list from the set of subset sums of $$$b$$$. If we let $$$[l, r]$$$ be the indices of the extra "centered" subarray in $$$b$$$, the largest remaining sum in the list must be the sum of $$$[1, r]$$$ in $$$b$$$ (or equivalently $$$[l, n + 2]$$$). If we let $$$x$$$ be this largest sum, and $$$y$$$ be the sum of $$$b$$$, we can use similar logic to the previous case to determine that the missing sum is $$$2x-y$$$.
So we can determine the missing sum, using the number of sums that appear an odd number of times in the input to determine which case we are in. Once we have found the missing sum, we just need to reconstruct $$$a$$$ using the process above. Also, notice that by the construction we have followed so far, the solution is always unique.
Complexity: $$$O(n^2 \log n)$$$