BITEXP - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Riddhish Lichade
Tester: Ram Agrawal
Editorialist: Prathamesh Sogale

DIFFICULTY:

EASY

PREREQUISITES:

Bitwise operations, XOR, OR

PROBLEM:

Vaibhav gave Meena two binary strings A and B of length N and M respectively (Note: Binary strings are the strings that can contain only two characters: ‘0’ and ‘1’). Vaibhav asked Meena to convert string A into string B by applying some operations (possibly zero). In one operation Meena can:

  • Take any two adjacent characters A_i and A_{i+1} of string A and calculate two values: 1. x=A_i ⊕ A_{i+1} and 2. $y=A_i ∨ A_{i+1}. Then he can replace one of the two A_i or A_{i+1} with x and the other one with y.

Note: ⊕ operation means bitwise XOR. The ∨∨ operation means bitwise OR operation.

Now, your task is to check if Meena can convert string A to string B.

EXPLANATION:

If the length of strings A and B are different then it’s not possible to convert string A into string B. Also check if the two strings are already equal. Now,

1 ∨ 0 = 1

1 ∨ 1 =1

1 ⊕ 0 = 1

1 ⊕ 1 = 0

We can observe that if we take XOR and OR of 2 numbers then at least one of them will always be 1. So we can observe that if 1 occurs in both the strings then then we can make both the strings equal by performing the given operations. So check if there is at least a single occurrence of ‘1’ in both the strings. If this is true then print “YES” else print “NO”.

SOLUTIONS:

Setter's Solution 
from sys import stdin
for _ in range(int(stdin.readline())):
    n, m = map(int, stdin.readline().strip().split())
    s1 = stdin.readline().strip()
    s2 = stdin.readline().strip()
    if (s1 == s2):
        print("YES")
        continue
    ans1 = ans2 = False
    if (n != m):
        print("NO")
        continue
    for i in s1:
        if (i == '1'):
            ans1 = True
            break
    for i in s2:
        if (i == '1'):
            ans2 = True
            break
    if (ans1 and ans2):
        print("YES")
    else:
        print("NO")