B. Flip the Bits | Codeforces Round 712 (Div. 2) | Solution C++

B. Flip the Bits
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a binary string  of length . In one operation, you can select any prefix of  with an equal number of 0 and 1 symbols. Then all symbols in the prefix are inverted: each 0 becomes 1 and each 1 becomes 0.

For example, suppose =0111010000.

  • In the first operation, we can select the prefix of length 8 since it has four 0's and four 1's: [01110100]00[10001011]00.
  • In the second operation, we can select the prefix of length 2 since it has one 0 and one 1[10]00101100[01]00101100.
  • It is illegal to select the prefix of length 4 for the third operation, because it has three 0's and one 1.

Can you transform the string  into the string  using some finite number of operations (possibly, none)?

Input

The first line contains a single integer  (1104) — the number of test cases.

The first line of each test case contains a single integer  (13105) — the length of the strings  and .

The following two lines contain strings  and  of length , consisting of symbols 0 and 1.

The sum of  across all test cases does not exceed 3105.

Output

For each test case, output "YES" if it is possible to transform  into , or "NO" if it is impossible. You can print each letter in any case (upper or lower).

Example
input
Copy
5
10
0111010000
0100101100
4
0000
0000
3
001
000
12
010101010101
100110011010
6
000111
110100
output
Copy
YES
YES
NO
YES
NO
Note

The first test case is shown in the statement.

In the second test case, we transform  into  by using zero operations.

In the third test case, there is no legal operation, so it is impossible to transform  into .

In the fourth test case, here is one such transformation:

  • Select the length 2 prefix to get 100101010101.
  • Select the length 12 prefix to get 011010101010.
  • Select the length 8 prefix to get 100101011010.
  • Select the length 4 prefix to get 011001011010.
  • Select the length 6 prefix to get 100110011010.

In the fifth test case, the only legal operation is to transform  into 111000. From there, the only legal operation is to return to the string we started with, so we cannot transform  into .


Solution :
We know that we always have to choose prefixes so we will start from the last and check if the current char is equal to the char in string b. If it is we will continue else we need to check whether we can choose a prefix and flip the bits.

Now if we flip the bits then all the bits before the current position will also get flipped, we will store this in our chng variable. If this is odd then we will flip the bit else not.

void solve() {

int n;
cin>>n;

string a,b;
cin>>a>>b;

vector<int>v;
int zero=0,one=0;

// to keep the difference of number of zero and one
for(int i=0; i<n; i++){
    a[i] == '1' ? ++one : ++zero;
    v.push_back(abs(one-zero));
}

int chng = 0;
for (int i = n - 1; i >= 0; i--)
{
// check whether this bit can flipped or not
    if(chng%2==1) a[i] == '1' ? a[i] = '0' : a[i] = '1';
    if(a[i]!=b[i]){
        if(v[i]==0){
            chng ++;
        }
        else {
            cout<<"NO\n";
            return;
        }
    }
}

cout<<"YES\n";

}

Post a Comment

0 Comments