Equal Multisets (Easy Version)

Key Observation

Look at two consecutive windows:

$$[a_{i-k+1},\ldots,a_i] \quad\text{and}\quad [a_{i-k+2},\ldots,a_{i+1}].$$

They differ only by removing $a_{i-k+1}$ and adding $a_{i+1}$. The same must be true for the corresponding windows of $b$.

Since both $b$ windows must match the corresponding $a$ windows as multisets, we get

$$\{b_{i+1}\}-\{b_{i-k+1}\} = \{a_{i+1}\}-\{a_{i-k+1}\}.$$

Because $a$ is a permutation, $a_{i+1}\ne a_{i-k+1}$. Therefore the signed multiset on the right has exactly one $+1$ value and exactly one $-1$ value. No funny business, no cancellation magic.

So we must have:

$$b_{i+1}=a_{i+1} \quad\text{and}\quad b_{i-k+1}=a_{i-k+1}.$$

As $i$ ranges from $k$ to $n-1$, this forces:

$$b_j=a_j \quad \text{for all } j\in[1,n-k]\cup[k+1,n].$$

What Is Not Forced?

The only indices not covered by those forced ranges are

$$[n-k+1,k].$$

This is exactly the intersection of all length-$k$ windows. If $2k\le n$, this interval is empty, so every position is forced and we only need $b_i=a_i$ wherever $b_i\ne -1$.

If $2k>n$, this middle interval exists. Let it be

$$C=[n-k+1,k].$$

Every length-$k$ window contains all positions of $C$. Outside $C$, we already know $b$ must equal $a$. Therefore, inside $C$, we only need the multiset of values to match:

$$\{b_i : i\in C\}=\{a_i : i\in C\}.$$

Since $a$ is a permutation, the values $a_i$ for $i\in C$ are all distinct. Thus the known non-$-1$ values inside $C$ must satisfy two conditions:

1. Each known value must belong to $\{a_i:i\in C\}$.
2. No known value may appear twice.

The remaining $-1$ positions can then be filled with the unused values from that same set. Clean. Almost annoyingly clean.

Algorithm

For each test case:

1. Compute

$$L=n-k+1,\quad R=k.$$

2. Mark all values $a_L,a_{L+1},\ldots,a_R$ as allowed middle values. If $L>R$, the middle is empty.
3. For every index $i$:
   • If $i\notin[L,R]$, then $b_i$ is forced. If $b_i\ne -1$ and $b_i\ne a_i$, answer NO.
   • If $i\in[L,R]$, then any known $b_i$ must be an allowed middle value and must not repeat.
4. If all checks pass, answer YES.

Correctness

For every pair of consecutive windows, validity implies

$$e_{b_{i+1}}-e_{b_{i-k+1}} = e_{a_{i+1}}-e_{a_{i-k+1}}.$$

Since $a_{i+1}\ne a_{i-k+1}$, this forces

$$b_{i+1}=a_{i+1},\qquad b_{i-k+1}=a_{i-k+1}.$$

Therefore all indices in $[1,n-k]\cup[k+1,n]$ must equal $a$.

The remaining interval $[n-k+1,k]$ is contained in every length-$k$ window. Once all outside positions match $a$, every window matches if and only if the middle interval has the same multiset as in $a$.

Our checks are exactly those necessary and sufficient conditions: outside values must match, and inside known values must form a subset without duplicates of the middle values of $a$. The unfilled spots can be assigned the remaining middle values.

Therefore the algorithm answers YES exactly when a valid completion exists.

Complexity

Each test case is processed in linear time:

$$O(n).$$

The memory usage is also

$$O(n).$$

Across all test cases, this is fine because

$$\sum n\le 2\cdot 10^5.$$