Prefix Suffix Reconstruction#12226

Problem Author:

Hasan Saleh (MathModel)

Prepared by:

Hasan Saleh (MathModel)

Edited by:

Hasan Saleh (MathModel)

Solution

Let's construct the array by the difference of and ,In general let be the construction of based on and let be the construction of based on , let x_1=a_1 and

\displaystyle x_i=p_{i+1}-p_i

for each (1 \le i \le n-1) , Same goes for the suffix sum , y_n=s_1 and

\displaystyle y_{n-i}=s_i-s_{i-1}

At the end of our construction , if x=y then there's a valid and it's correct and we consider it.

for _ in range(int(input())):
    n=int(input())
    p=list(map(int,input().split()))
    s=list(map(int,input().split()))
    a=[0]*n
    b=[0]*n
    a[0]=p[0]
    b[n-1]=s[0]
    for i in range(1,n):
        a[i]=p[i]-p[i-1]
        b[n-1-i]=s[i]-s[i-1]
    if(a==b):
        print(*a)
    else:
        print(-1)

Complexity .