Plus and Minus

Practice

5 (8 votes)

Algorithms

Binary search

Problem

73% Success 782 Attempts 30 Points 3s Time Limit 256MB Memory 1024 KB Max Code

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

Sample Input

2
8
8 5 3 2 2 1 1 1
8
8 7 6 5 4 3 2 1

Sample Output

YES
2 1
NO

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.

Code Editor

You need to be logged in to access the code editor

Please wait while we load the editor

Submissions

Please login to view your submissions

You need to be logged in to access the code editor

Please wait while we load the editor