Prefiks Suffix Yenidənqurması#12226

Prefiks Suffix Yenidənqurması (Həll təhlili)

Problem Müəllifi:	Hasan Saleh (MathModel)
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	Hasan Saleh (MathModel)

Həll

Gəlin $a$ massivini $p$ və $s$ arasındakı fərqlə quraq, Ümumiyyətlə $x$ -i $p$ -yə əsaslanaraq $a$ -nın qurulması kimi götürək və $y$ -ni $s$ -yə əsaslanaraq $a$ -nın qurulması kimi götürək, $x_{1} = a_{1}$ x_1=a_1 və

x_{i} = p_{i + 1} - p_{i}

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

hər $(1 \leq i \leq n - 1)$ (1 \le i \le n-1) üçün, Eyni şey suffix cəmi üçün də keçərlidir, $y_{n} = s_{1}$ y_n=s_1 və

y_{n - i} = s_{i} - s_{i - 1}

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

Qurulma prosesimizin sonunda, əgər $x = y$ x=y olarsa, onda etibarlı bir $a$ var və bu doğrudur və biz bunu nəzərə alırıq.

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)

Python

Komplekslik $O (n)$ .