SWAPFLIP - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author:
Tester: apoorv_me
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You have a binary string S. In one move, you can either swap any two of its characters, or flip any two of its characters.
Can S be turned into T?

EXPLANATION:

Swapping any two characters allows us to essentially rearrange the characters of S however we like. So, as long as S and T contain the same number of zeros and ones, we’ll be able to make them equal.
If S and T don’t have the same number of zeros and ones it’s obviously impossible for them to be equal. So, our goal is to make these counts equal.

Next, we look at the flip operation. Suppose we flip S_i and S_j. Then,

  • If S_i=0 and S_j=1 (or vice versa), flipping both is equivalent to swapping them. This gives us nothing new, so we can ignore it.
  • If S_i=S_j=0, we convert two zeros into ones. Similarly, if S_i=S_j=1, we convert two ones to zeros.
    Note that we effectively change the number of zeros and ones by +2/-2 using these moves.

Let s_0 and t_0 be the number of zeros in S and T, respectively.
We want s_0 = t_0 to hold (note that this automatically makes their number of ones be equal, since lengths are the same).

As noted above, s_0 can only be changed by +2 or -2 using flip operations.
So, if (s_0 - t_0) is even, the two values can be made equal (by repeatedly adding or subtracting 2 till the difference becomes zero); and if it’s odd they can never become equal.

Thus, the answer is simply Yes if $(s_0 - t_0)is even, andNo` otherwise.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    s = input()
    t = input()
    
    zs, zt = s.count('0'), t.count('0')
    if zs%2 == zt%2: print('Yes')
    else: print('No')
2 Likes
2

This is good problem.

3

equating xor also works