Fake Swaps solution codechef

Fake Swaps solution codechef

You are given two binary strings SS and PP. You need to convert SS into PP using the following operation any number of times (possibly zero):

  • Pick three binary values XXYY, and ZZ, such that at least one of them is equal to 11 and at least one of them is equal to 00. Then, pick three distinct indices iijj, and kk, and assign Si=XSi=XSj=YSj=Y, and Sk=ZSk=Z.

Determine whether it’s possible to convert SS into PP.

Fake Swaps solution codechef

  • The first line contains an integer TT denoting the number of test cases. The TT test cases then follow.
  • The first line of each test case contains NN denoting the length of SS and PP.
  • The second line of each test case contains SS.
  • The third line of each test case contains PP.

Output Format

For each test case, output on one line YES if it is possible to convert SS to PP, or NO if it is not possible to do so. Output is case insensitive.

Fake Swaps solution codechef

  • 1T10001≤T≤1000
  • 3N10003≤N≤1000
  • |S|=|P|=N|S|=|P|=N

Fake Swaps solution codechef



Sample Output 1 



  • For the first test case, we choose X=0,Y=1X=0,Y=1 and Z=1Z=1. This satisfies the above condition. Three indices (i,j,k)(i,j,k) are chosen as (1,2,4)(1,2,4), and (A1,A2,A4)(A1,A2,A4) are then assigned as (0,1,1)(0,1,1) respectively. After this operation, SS transforms into 0101.

  • For the second test case, no set of any operations is possible to make SS equals to PP.

Leave a Comment

Your email address will not be published.