Hints: Equal Multisets (Hard Version)

Read the easy version first: sliding windows of length $k$ link positions in the same residue class modulo $k$. Why does fixing one window constrain the next?

Answer to Hint 1: Two consecutive $k$-windows share $k-1$ elements, so the multiset of the new element on the right must balance multiset differences. Along each residue class $r \pmod k$, comparing $a$ at $r, r+k, \ldots$ tells you whether $b$ is forced to track $a$ or only to be constant on that progression.

Answer to Hint 2: For each $r \in {0, \ldots, k-1}$ (using $0$-based indexing in code):

• If $a_r, a_{r+k}, \ldots$ are not all equal, then cool arrays force $b$ at those indices to match $a$ (after replacing $-1$). Any contradiction with a known $b$ fails.

• If they are all equal, then either all known $b$ on that progression agree (and fill $-1$ with that value), or there is no known $b$ yet.

Answer to Hint 3: After this sweep, every $-1$ that could be determined locally along a non-constant class is fixed; constant classes either get a unanimous value or stay free until the global check.

What global constraint involves only the first $k$ positions?

Answer to Hint 4: The multiset of $a[1..k]$ must equal the multiset of $b[1..k]$ after replacements. Count multiplicities of values in $a[1..k]$, then for each $i \le k$ with $b_i \neq -1$, decrement the count for $b_i$. If you ever need a value with count $0$, answer NO.

Why are remaining $-1$s in the prefix automatically satisfiable if this never fails?

Answer to Hint 5: Any still-unknown entries in the prefix can be filled with the unused multiset elements arbitrarily; earlier steps ensured consistency along each residue class with the sliding-window condition.

The easy version is the special case where $a$ is a permutation, which simplifies counting but not the residue-class logic.