公式

F - Contrast 解説 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++)

投稿日時:
最終更新: