You are given two arrays \(a = [a_1, a_2, ..., a_n]\) and \(b = [b_1, b_2, ..., b_n]\), with \(a_1 = a_2 = ... = a_n = 0\).
First, you must choose two of indices \(i, j\) (\(1 \leq i, j \leq n, i \neq j\)) and assign \(a_i = a_j = 1\).
Then perform the following operation as many times as you want:
- Choose an index \(k (1 \leq k \leq n)\), and add the product of the two largest integers in \(a\) to \(a_k\). That is, \(a_k = a_k + a_i \cdot a_j\), where \(a_i \geq a_j \geq a_l\) for all \(l (1 \leq l \leq n, l \neq i, l \neq j)\).
Now, determine if you can transform the array \(a\) into the array \(b\) or not.
If you can construct the array, then print “YES”. Otherwise, print “NO”.
Constraints
- \(1 \leq T \leq 1000\)
- \(2 \leq n \leq 10^5\)
- \(0 \leq b_i \leq 10^9\)
Input Format
- The first line contains a single integer \(T\) —- the number of test cases.
- For each testcase:
- The first line contains one integer \(n\) —- the length of the arrays.
- The second line contains \(n\) nonnegative integers \(b_1, b_2, ... , b_n\).
- The sum of \(n\) over all test cases does not exceed \(10^6\).
Output Format
- For each Testcase, output "YES" if the array \(a\) can be transformed into \(b\). Otherwise, output "NO".
3 4 8 1 0 0 4 5 2 2 0 4 6 3 0 0
YES YES NO
In the first case:
- \(a = [0,0,0, 0]\) initially.
- Assign \(a_1 = a_2 = 1\), so \(a = [1, 1, 0, 0]\).
- Operation with \(k = 1\), after the opertaion \(a = [2, 1, 0, 0]\).
-
Operation with \(k = 1\), after the opertaion \(a = [4, 1, 0, 0]\).
-
Operation with \(k = 1\), after the opertaion \(a = [8, 1, 0, 0]\).
In the second case:
- \(a = [0,0,0, 0]\) initially.
- Assign \(a_1 = a_2 = 1\), so \(a = [1, 1, 0, 0]\).
- Operation with \(k = 2\), after the opertaion \(a = [1, 2, 0, 0]\).
-
Operation with \(k = 3\), after the opertaion \(a = [1, 2, 2, 0]\).
-
Operation with \(k = 1\), after the opertaion \(a = [5, 2, 2, 0]\).
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor