FSTS - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: pols_agyi_pols
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You’re given a binary string S. In one move, you can choose two distinct indices i, j such that S_i = S_j = 1, and turn both indices to 0.
Is it possible to turn S into T?

EXPLANATION:

Our operation only allows us to turn a 1 in S into a 0.
So, if there’s some index i such that S_i = 0 but T_i = 1, it’s impossible to turn S into T.

This means there are only three types of indices:

  1. S_i = T_i = 0
  2. S_i = T_i = 1
  3. S_i = 1 and T_i = 0

The first type can’t be changed by us, and the second type shouldn’t be changed (since doing so would make S_i = 0 and T_i = 1).
As for the third type, all of them must be modified to make S equal to T.

However, in one operation we can change exactly two indices.
This means we can only change an even number of indices, and not an odd number.
So, if the number of type-3 indices is even, the answer is "Yes", otherwise the answer is "No".

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    s = input()
    t = input()
    
    change, bad = 0, 0
    for i in range(n):
        if s[i] != t[i]:
            change += 1
            if s[i] == '0': bad = 1
    
    if bad or change%2 == 1: print('No')
    else: print('Yes')