Hints: Equal Multisets (Easy Version)

“Cool” means: for every window of length $k$, the multiset of $a$ on that window equals the multiset of $b$ on the same indices. For $i \ge k$, how does window $[i-k+1, i]$ overlap with window $[i-k+2, i+1]$ when you slide by one?

Answer to Hint 1: Consecutive windows of length $k$ share $k-1$ positions. So values of $a$ (and hence $b$) on positions that are congruent modulo $k$ are tightly linked: along each residue class $r \pmod k$, the multiset constraints force strong relations between $b_{r}, b_{r+k}, b_{r+2k}, \ldots$.

Answer to Hint 2: Fix a residue $r$. Look at indices $r, r+k, r+2k, \ldots$. Compare $a$ at those positions.

If not all $a$ on that arithmetic progression are equal, what must hold for $b$ on those indices once the array is cool?

Answer to Hint 3: If $a$ varies along the class, each window of length $k$ pins $b$ at those positions to match the corresponding $a$ values (up to filling $-1$). Unknowns in $b$ on that class must be set to the same values as $a$ at those indices; any mismatch with a known $b$ yields NO.

Answer to Hint 4: If all $a$ on that progression are equal to some value $v$, then every length-$k$ window only forces that all known $b$ on that progression agree with each other (and with $v$ when revealed). If some $b$ is fixed, all $-1$s on that progression take that value; if none are fixed, leave them for later.

What is still unchecked after resolving every residue class this way?

Answer to Hint 5: The first $k$ positions form the initial window. After substitutions, treat the multiset of assigned values on $b[1..k]$ against $a[1..k]$: each known $b_i$ must use up one copy of that value in the multiset of $a$’s first $k$ elements (in the easy version, $a$ is a permutation, so multiplicity is easy to track).

If some required value is impossible, answer NO; else YES.

Answer to Hint 6: The hard version relaxes “$a$ is a permutation” but the same residue-class logic applies; only the final multiset check on the prefix differs when duplicates exist.