Plus and Minus

★★★★★

8 votes

Algorithms, , Binary Search

Details

Submissions

Discussion

Editorial

Problem

Initially, you have an array of length $2$ , which is $a = [a_1, a_2]$ . Here $a_1 \geq a_2 \geq 0$ .

In each step, you must choose the two largest integers $a_i$ and $a_j$ in the array, where $a_i \geq a_j$ , and insert two integers $a_i + a_j$ and $a_i - a_j$ to the array (in any positions).

Thus, you can construct an array of any even length $\geq 4$ .

Now you are given an array of even length $N$ .

Please determine whether you can form this array by the steps. If so, then find out which is the initial array.

Constraints

$1 \leq T \leq 1000$
$4 \leq N \leq 10^7$
$0 \leq a_i \leq 10^9$
The sum of $N$ across all test cases does not exceed $10^7$ .

Input Format

The first line contains a single integer $T$ —- the number of test cases.
For each testcase:
- The first line contains one odd integer $N$ —- the length of the arrays.
- The second line contains $N$ positive integers $a_1, a_2, ... , a_N$ .
The sum of $N$ over all test cases does not exceed $10^7$ .

Output Format

For each testcase, output " $YES$ " if you can construct the given array by the steps. Otherwise, output " $NO$ ".
If you can construct such an array, then print two integers $a_1, a_2$ . Note that $a_1 \geq a_2$ .

Time Limit: 3

Memory Limit: 256

Source Limit:

Explanation

In the first case:

Assume that the initial array is $a = [2, 1]$ .
In the first step, we add $2 + 1 = 3$ and $2 - 1 = 1$ to the array, and so the array becomes $[3, 2, 1, 1]$ .
In the second step, we add $3 + 2 = 5$ and $3 - 2 = 1$ to the array, and so the array becomes $[5, 3, 2, 1, 1, 1]$ .
In the third step, we add $5 + 3 = 8$ and $5 - 3 = 2$ to the array, and so the array becomes $[8, 5, 3, 2, 2, 1, 1, 1]$ .

In the second case:

If you can construct the given array, there exists the initial array $a = [a_1, a_2]$ with $a_1 \geq a_2$ .
Since there is no removal in any step, $a_1$ and $a_2$ are in the given array.
However, by considering all possible arrays of length $2$ , you can find there is no way to construct this array.