Array Construction

Practice

5 (2 votes)

Basics of hash tables

Data structures

Hash tables

Problem

54% Success 429 Attempts 30 Points 1.5s Time Limit 256MB Memory 1024 KB Max Code

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".

Sample Input

Sample Output

YES
YES
NO

Explanation

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

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