+ , -- və ya ?#12270

+ , -- və ya ? (Həll təhlili)

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

Həll

İlk öncə massivi uzunluğu $n - 1$ n-1 olan bir string $t$ -yə çeviririk:

t_{i} = ⎩ ⎨ ⎧ + - ? əgər a_{i} < a_{i + 1}, əgər a_{i} > a_{i + 1}, əgər a_{i} = a_{i + 1} .

t_i = \begin{cases} \texttt{+} & \text{əgər } a_i < a_{i+1},\\ \texttt{-} & \text{əgər } a_i > a_{i+1},\\ \texttt{?} & \text{əgər } a_i = a_{i+1}. \end{cases}

İndi problem budur: $s$ $t$ -nin alt stringi olaraq görünürmü, uyğunluq qaydası altında

t_{i + j} = ? və ya s_{j} = ? və ya t_{i + j} = s_{j} .

t_{i+j} = \texttt{?} \;\;\text{və ya}\;\; s_j = \texttt{?} \;\;\text{və ya}\;\; t_{i+j} = s_j.

Məhdudiyyətlər kiçik olduğuna görə, sadəcə hər bir başlanğıc mövqeyini yoxlaya bilərik. $0 \leq i \leq (n - 1) - k$ 0 \le i \le (n-1)-k olan hər bir $i$ üçün $0$ -dan $k - 1$ k-1-ə qədər bütün $j$ -ləri yoxlayırıq. Əgər hər hansı bir $j$ üçün yuxarıdakı şərt pozulursa, bu pəncərə pisdir. Əgər bütün $j$ üçün bu şərt yerinə yetirilən bir pəncərə tapsaq, cavabımız BƏLİ olacaq. Əgər heç bir pəncərə işləmir, cavabımız XAHİŞ ETMİRƏM olacaq.

Rəsmi olaraq, biz BƏLİ cavabını veririk əgər

\exists i \forall j \in [0, k - 1] : (t_{i + j} = ? \lor s_{j} = ? \lor t_{i + j} = s_{j}) .

\exists i \;\; \forall j \in [0,k-1]: \bigl(t_{i+j} = \texttt{?} \lor s_j = \texttt{?} \lor t_{i+j} = s_j \bigr).

Hər test üçün mürəkkəblik $O (nk)$ -dir: $t$ -ni qurmaq $O (n)$ alır, və biz ən çox $n$ pəncərəni yoxlayırıq, hər biri $O (k)$ -də. Bu, $\sum n \cdot k$ \sum n\cdot k üçün verilmiş sərhədi uyğunlaşdırır. Nümunə testləri bu qaydadan birbaşa gəlir: massivin fərq stringi bəzi '?'-ni '+' və ya '-' kimi şərh edərək naxış kimi oxuna bilirsə, cavabımız BƏLİ olacaq; əks halda, XAHİŞ ETMİRƏM olacaq.

Mürəkkəblik $O (nk)$ .

def solve():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    s=input().strip()
    t=[]
    for i in range(n-1):
        if a[i]<a[i+1]: t.append('+')
        elif a[i]>a[i+1]: t.append('-')
        else: t.append('?')
    ok=False
    for i in range(n-1-k+1):
        good=True
        for j in range(k):
            x=t[i+j]; y=s[j]
            if x=='?' or y=='?': continue
            if x!=y:
                good=False
                break
        if good:
            ok=True
            break
    print("BƏLİ" if ok else "XAHİŞ ETMİRƏM")

for _ in range(int(input())):
    solve()

Python