Official

A - Dot Product Editorial by evima

Let \(\displaystyle C_i=\frac{A_i}{B_i}\).

If all values of \(C_1,C_2,\ldots,C_N\) are the same, then the answer is No. This is because, letting \(C=C_i>0\), we have \(\displaystyle \sum_{i=1}^N A_iX_i=C\sum_{i=1}^N B_iX_i\), which means \(\displaystyle \sum_{i=1}^N A_iX_i\) and \(\displaystyle \sum_{i=1}^N B_iX_i\) always have the same sign.

Conversely, if not all values of \(C_1,C_2,\ldots,C_N\) are the same, then the answer is Yes. More specifically, when we take a pair of indices \((i,j)\) such that \(C_i \neq C_j\), we can construct the solution as follows:

  • If \(C_i < C_j\), set \(X_i=-(A_j+B_j),\ X_j=A_i+B_i\), and set all other values to \(0\).

  • If \(C_i > C_j\), set \(X_i=A_j+B_j,\ X_j=-(A_i+B_i)\), and set all other values to \(0\).

Proof

Consider the case where $C_i < C_j$.

$\displaystyle \sum_{k=1}^N A_kX_k = A_iX_i+A_jX_j=-A_i(A_j+B_j)+A_j(A_i+B_i)=A_jB_i-A_iB_j=B_iB_j\left(C_j-C_i \right)>0,$

$\displaystyle \sum_{k=1}^N B_kX_k = B_iX_i+B_jX_j=-B_i(A_j+B_j)+B_j(A_i+B_i)=A_iB_j-A_jB_i=B_iB_j\left(C_i-C_j \right)<0$

This follows from the above.

The case where $C_i > C_j$ can be shown similarly.

By implementing the above appropriately, we can solve this problem correctly. The time complexity is \(O(N)\) for each test case.

Sample Implementation (Python3)

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    k = -1
    for i in range(1, n):
        if a[i] * b[0] != b[i] * a[0]:
            k = i
            break
    if k == -1:
        print("No")
        continue
    x = [0] * n
    x[0] = a[i] + b[i]
    x[i] = a[0] + b[0]
    if a[0] * b[i] > a[i] * b[0]:
        x[i] *= -1
    else:
        x[0] *= -1
    print("Yes")
    print(*x)

posted:
last update: