Official

C - Even Sum Triplet Editorial by evima


There are two kinds of operations: one on two odd terms and one even term, and one on three even terms. Performing an operation does not affect the availability of the former, so the answer is No if it can be done in \(A\) but not in \(B\), or vice versa.

[1] If odd terms cannot be moved in both \(A\) and \(B\)

In this case, the odd terms in \(A\) must coincide with those in \(B\) for the answer to be Yes. If they do, we may split the sequences at the odd terms to reduce the problem into the case that all terms are even.

If all terms are even, one can swap any two adjacent terms if the length of the sequence is at least \(3\). Thus,

  • if the length is \(2\) or less, the answer is Yes if and only if \(A\) and \(B\) are equal as sequences;
  • if the length is \(3\) or greater, the answer is Yes if and only if \(A\) and \(B\) are equal as multisets.

[2] If odd terms can be moved in both \(A\) and \(B\)

The operation is reversible, so we may consider whether \(A\) and \(B\) can be turned into the same sequence to solve the problem.

First, let us try to move all odd numbers to the beginning of the sequence. If \(A_i, A_{i+1},\ \dots, A_{i+k-1}\ (2 \leq k)\) are odd and \(A_{i+k}\) is even, one can repeat the operation to rearrange them into \(A_{i+k},\ A_i,\ A_{i+1},\ \dots,\ A_{i+k-1}\). Repeating this process can move all odd numbers to the beginning of the sequence. (If there are no two adjacent odd numbers initially, create them by an operation involving odd terms.)

After separating the odd and even terms, can we sort the odd terms? For instance, if \(A_1,\ A_2,\ \dots,\ A_k\) are odd and \(A_{k+1},\ A_{k+2},\ \dots,\ A_N\) are even, can we swap \(A_i\) and \(A{i+1}\ (i < k)\)? The answer is yes: you can move the even \(A_{k+1}\) one by one as \(A_{k-1},\ A_{k},\ A_{k+1} \rightarrow A_{k-1},\ A_{k+1},\ A_{k}\) to make the arrangement \(A_{i},\ A_{i+1},\ A_{k+1}\), perform the swap as \(A_{i},\ A_{i+1},\ A_{k+1} \rightarrow A_{i+1},\ A_i,\ A_{k+1}\), and then put \(A_{k+1}\) to the original position. Thus, any two adjacent odd terms can be swapped, so we can sort all odd terms. For even terms, if there are three or more of them, any two adjacent ones can be swapped, so we can sort all even terms. If there are two, we cannot perform an operation involving both, so they cannot be swapped.

Therefore,

  • if the number of even numbers in each of \(A\) and \(B\) is not \(2\), the answer is Yes if and only if \(A\) and \(B\) are equal as multisets;
  • if the number of even numbers in each of \(A\) and \(B\) is \(2\), the answer is Yes if and only if \(A\) and \(B\) are equal as multisets and contain the two even numbers in the same order.

One can check the availability of the operation involving odd numbers in \(O(N)\) time, and the equality of multisets in \(O(N\log N)\) time, which is fast enough.

posted:
last update: