Contest Duration: - (local time) (100 minutes) Back to Home

## F - Contrast Editorial by evima

If a value appears more than $$N+1$$ times in $$A$$ and $$B$$ overall, then the answer is No by Pigeonhole Principle. We(will consider otherwise.)

Let $$C[i]$$ be the number of elements less than or equal to $$i$$ that appears in $$A$$, and $$D[i]$$ be the number of elements less than or equal to $$i$$ that appears in $$B$$. $$C$$ and $$D$$ are non-decreasing, and each of $$C[i]$$ and $$D[i]$$ is an integer between $$0$$ and $$N$$, inclusive.

For each integer $$x(0 \leq x \leq N)$$, let us consider shifting $$B$$ for $$x$$ elements to the right (that is, shifting each $$B[i+1]$$ to $$B[(i+x)\%N+1]$$).

The conditions that $$x$$ must satisfies is that, for all $$i(1 \leq i \leq N$$, three segments $$(C[i-1],C[i]],(x+D[i-1],x+D[i]]$$ and $$(N+C[i-1],N+C[i]]$$ do not overlap with each other. This conditions are equivalent to $$C[i]-D[i-1] \leq x \leq C[i-1]+N-D[i]$$ for all $$i(1 \leq i \leq N)$$.

Also, we can prove that such $$x$$ always exists. (*1)

The conditions above can is equivalent to the condition where $$x$$ is between the maximum of $$C[i]-D[i-1]$$ and the minimum of $$C[i-1]+N-D[i]$$, inclusive, so specifically when $$x$$ is the maximum of $$C[i]-D[i-1]$$, it satisfies the conditions.

Therefore, when $$B$$ is shifted to the right for the maximum of $$C[i]-D[i-1]$$, that will be the desired permutation of $$B$$ that satisfies the original conditions, and therefore the answer is always Yes. The total time complexity is $$O(N)$$.

Proof of (*1)

Assume that we have $$(i, j)$$ such that $$C[i]-D[i-1] > C[j-1]+N-D[j]$$, and we will show the contradiction.

• When $$i \leq j-1$$, $$C[i] \leq C[j-1]$$ hence $$D[j]-D[i-1] > N$$, but the difference of two integers between $$0$$ and $$N$$ cannot be more than $$N$$, so it’s contradiction.

• When $$i-1 \geq j$$, $$-D[i-1] \leq -D[j]$$ hence $$C[i]-C[j-1] > N$$, but the difference of two integers between $$0$$ and $$N$$ cannot be more than $$N$$, so it’s contradiction.

• When $$i = j$$, $$C[i]-C[i-1]+D[i]-D[i-1] > N$$, but it contradicts to the fact the number of $$i$$ in $$A, B$$ is at most $$N$$.

Sample Code（C++）

Also, there is a greedy solution of time complexity $$O(N)$$.

Sample Code（C++）

posted:
last update: