LEX - Editorial

PROBLEM LINK:

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

Author: gg98
Tester: mexomerf
Editorialist: iceknight1093

DIFFICULTY:

simple

PREREQUISITES:

None

PROBLEM:

You’re given two strings S and T, containing only the characters A and B.
You can perform the following operation on S:

  • Choose an index i such that S_i \neq S_{i+3} and S_{i+1} = S_{i+2}, and delete S_{i+1} and S_{i+2} from S.
    The remaining characters are concatenated together, and the length of S decreases by 2.

EXPLANATION:

Analyzing the operation, we observe that it essentially allows us to turn \text{AAAB} and \text{ABBB} into \text{AB}, and \text{BAAA} and \text{BBBA} into \text{BA}.

Let’s try to reverse the operation and apply it on T instead, and see if we can obtain S.
The reverse operation is to take two adjacent unequal characters in T, and insert either two A's or two B's between them.

Let’s look at T in terms of maximal contiguous blocks of A's and B's.
For example, if T = \text{AABBBABBAAA}, the blocks are \text{AA, BBB, A, BB, AAA}.

Observe that our operation is equivalent to being able to take any non-empty block and increase its length by 2.
In particular, this means that it’s impossible to change the number of blocks, and it’s also impossible to change the parity of the length of the block.

Now, two strings are equal if and only if their corresponding blocks are equal.
Let s_1, s_2, \ldots, s_k be the block lengths of S, and t_1, t_2, \ldots, t_m be the block lengths of T.

Then,

  • If k \neq m, we cannot turn T into S since the block counts don’t match and cannot be changed.
  • If S_1 \neq T_1, we again cannot turn T into S - the blocks will alternate between A's and B's, so if their count is equal, the types of the all blocks will match if and only if the first blocks are of the same type.
  • As noted above, the only change we can make is increasing some t_i by 2, and our goal is to have s_i = t_i for every i.
    This is only possible if every (s_i - t_i) is a non-negative even integer, which is easy to check.

There is one edge case: if T has only a single block, it’s not actually possible to operate on T at all since the operation requires two adjacent unequal characters.
So, in this case alone, the answer is Yes if and only if S = T initially - any other case is a No, even if all the earlier conditions are satisfied.
For example, if S = \text{AAA} and T = \text{A} the answer should be No.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Author's code (C++)
#include <bits/stdc++.h>
using namespace std;

int main() {
	// your code goes here
	int tt;
	cin>>tt;
	while(tt>0)
	{
        int n,m;
        cin>>n>>m;
        string s,t;
        cin>>s>>t;
        vector<int>a,b;
        int cnt=1;
        for(int i=1;i<n;i++)
        {
            if(s[i]==s[i-1])
            cnt++;
            else
            {
                if(s[i-1]=='B')
                cnt=-cnt;
                a.push_back(cnt);
                cnt=1;
            }
        }
        if(s[n-1]=='B')
        cnt=-cnt;
        a.push_back(cnt);
        cnt=1;
        for(int i=1;i<m;i++)
        {
            if(t[i]==t[i-1])
            cnt++;
            else
            {
                if(t[i-1]=='B')
                cnt=-cnt;
                b.push_back(cnt);
                cnt=1;
            }
        }
        if(t[m-1]=='B')
        cnt=-cnt;
        b.push_back(cnt);
        if(a.size()!=b.size())
        {    cout<<"NO\n";
        }
        else
        {
            if(a.size()==1&&a[0]!=b[0])
            cout<<"NO\n";
            else
            {
                bool ans=true;
                for(int i=0;i<a.size();i++)
                {
                    if(a[i]>0&&b[i]<0)
                    ans=false;
                    if(a[i]<0&&b[i]>0)
                    ans=false;
                    if(abs(a[i])<abs(b[i]))
                    ans=false;
                    if(abs(a[i])%2!=abs(b[i])%2)
                    ans=false;
                }
                if(ans)
                cout<<"YES\n";
                else
                cout<<"NO\n";
            }
        }
        tt--;
	}

}

Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
void block(string s, vector<int> &v){
    char c = s[0];
    int cnt = 1;
    for(int i = 1; i < s.size(); i++){
        if(s[i] == c){
            cnt++;
        }else{
            v.push_back(cnt);
            cnt = 1;
            c = s[i];
        }
    }
    v.push_back(cnt);
}
int main() {
	int t;
	cin>>t;
	while(t--){
	    int n, m;
	    cin>>n>>m;
	    string s, t;
	    cin>>s>>t;
	    bool f = true;
	    for(int i = 0; i < n; i++){
	        if(s[i] != s[0]){
	            f = false;
	            break;
	        }
	    }
	    if(f){
	        if(s == t){
	            cout<<"YES\n";
	        }else{
	            cout<<"NO\n";
	        }
	    }else{
	        if(s[0] != t[0]){
	            cout<<"NO\n";
	        }else{
	            vector<int> a, b;
	            block(s, a);
	            block(t, b);
	            bool f = true;
	            if(a.size() != b.size()){
	                f = false;
	            }else{
	                for(int i = 0; i < a.size(); i++){
	                    if((a[i] < b[i]) || ((a[i] - b[i]) % 2 == 1)){
	                        f = false;
	                        break;
	                    }
	                }
	            }
	            if(f){
	                cout<<"YES\n";
	            }else{
	                cout<<"NO\n";
	            }
	        }
	    }
	}
}

Editorialist's code (PyPy3)
for _ in range(int(input())):
    n, m = map(int, input().split())
    s = input().strip()
    t = input().strip()
    sblock, tblock = [], []
    p = 0
    for i in range(1, n):
        if s[i] != s[i-1]:
            sblock.append(i - p)
            p = i
    sblock.append(n - p)
    p = 0
    for i in range(1, m):
        if t[i] != t[i-1]:
            tblock.append(i - p)
            p = i
    tblock.append(m - p)
    
    if len(sblock) != len(tblock):
        print('No')
        continue
    
    if s[0] != t[0]:
        print('No')
        continue
    
    ans = 'Yes'
    for i in range(len(sblock)):
        x, y = sblock[i], tblock[i]
        if x%2 != y%2 or x < y: ans = 'No'
    
    if len(sblock) == 1 and n != m: ans = 'No'
    print(ans)

Actually, I tried a solution which passed the test, but I don’t have any clue on how to prove it.

The solution is to greedily execute the operation from left to right whenever possible, for both S and T.

If the resulting S’ and T’ are equal, then the answer is YES.

Anyone can help prove it?

Don’t know about how to prove things but no matter you greedily do it or randomly execute operations until possible the resulting string will always be the same, even number of consecutive A’s or B’s become AA or BB and odd number becomes A or B if the string contains atleast one A and B , otherwise we can’t do any operations at all, hope you get it

I tried to solve this question but I am not getting why my code fails even on the shown test cases. I tried to remove pairs whenever possible from ‘s’ string to match the ‘t’ string. It would be really great, if someone could help me with my code to understand what am I missing. Thank you in advance.
I’ve attached my code.

#include <bits/stdc++.h>
using namespace std;

int main() {
	int t;
	cin >> t;
	while (t--) {
	    int n, m;
	    cin >> n >> m;
	    string s, t;
	    cin >> s;
	    cin >> t;
	    string result = "NO";

	    if (s == t) result = "YES";
	    if (result == "YES") {
	        cout << result << endl;
	        continue;
	    }
	    if (s[0] != t[0]) {
	        cout << result << endl;
	        continue;
	    }
	    
	    int i = 0,j = 3;
	    int prev;
	    while (i < t.size() && j < s.size()) {
	       // cout << s << endl;
	       // cout << i << j << endl;
	        prev = i;
	        if (s[i] == t[i]) {
	            i++;
	            j++;
	           // cout << "same" << endl;
	            continue;
	        }
	        
	        prev--;
	        if (s[prev + 1] == s[prev + 2] && s[prev] != s[j]) {
	            
	            s = s.substr(0, prev + 1) + s.substr(j - 1, s.size() - j);
	           // s = s.substr(0, j - 2) + s.substr(j, s.size() - j);
	            j = i + 3;
	           // cout << "removed" << endl;
            }
            else {
                cout << s[prev - 1] << s[prev + 1] << s[prev + 2] << s[j] << endl;
                i++;
                j++;
                // cout << "condition not satisfied" << endl;
            }
            if (s == t) {
                result = "YES";
                break;
            }
	    } 
	    cout << result << endl;
	}
}