+ , -- or ? (Editorial)

Solution

We first convert the array to a string $t$ of length n-1 as follows:

Now the problem is: does $s$ appear as a substring of $t$ under the matching rule

Because the constraints are small , we can simply try every starting position. For every $i$ with 0 \le i \le (n-1)-k we check all $j$ from $0$ to k-1. If for some $j$ the above condition fails, then this window is bad. If we find a window for which it holds for all $j$, we answer YES. If none of the windows works, we answer NO.

Formally, we answer YES iff

The complexity per test is $O(nk)$: building $t$ takes $O(n)$, and we check at most $n$ windows, each in $O(k)$. This fits the given bound on \sum n\cdot k. The sample tests follow directly from this rule: whenever the array-difference string can be read as the pattern after interpreting some '?' as '+' or '-', the answer is YES; otherwise it is NO.

Complexity $\mathcal{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("YES" if ok else "NO")

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