Official

B - Swap If Equal Sum Editorial by evima


Since the sum of the sequence is invariant under operations, if \(\sum_{i=1}^{N}{A_i}\) and \(\sum_{i=1}^{N}{B_i}\) are different, the answer is \(\text{No}\). If \(A=B\), the answer is clearly \(\text{Yes}\). Consider the case otherwise. When \(\sum_{i=1}^{N}{A_i}\) is at least \(2\), by repeating the following operations:

  • swap \(\{1,0\}\) with \(\{1\}\) at a position to its right
  • swap \(\{0,1\}\) with \(\{1\}\) at a position to its right

we can transform the sequence into the form \(\{1,1,\dots,1,0,0,\dots,0\}\). After performing this operation on \(A\), we can make \(A\) match \(B\) by performing the reverse sequence of operations that transforms \(B\) to this canonical form. When \(\sum_{i=1}^{N}{A_i}=1\), if \(A_1\) or \(A_N\) is \(1\), no valid operation can be performed, so the answer is \(\text{No}\). Similarly, if \(B_1\) or \(B_N\) is \(1\), the answer is \(\text{No}\). Otherwise, the operation of swapping \(\{0\}\) and \(\{0,0\}\) is possible, so \(A\) can be made to match \(B\).

posted:
last update: