Reconstrucción de Prefijos y Sufijos (Editorial)

Solución

Construyamos el arreglo $a$ mediante la diferencia de $p$ y $s$. En general, dejemos que $x$ sea la construcción de $a$ basada en $p$ y dejemos que $y$ sea la construcción de $a$ basada en $s$, dejemos que x_1=a_1 y

para cada (1 \le i \le n-1). Lo mismo ocurre con la suma de sufijos, y_n=s_1 y

Al final de nuestra construcción, si x=y, entonces hay un $a$ válido y es correcto y lo consideramos.

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)

Complejidad $\mathcal{O}(n)$.