DISTDEST - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest

Author: Kunal Nehra
Tester: Abhishek Ghosh
Editorialist: Aman Muhal, Gaurav Garg

DIFFICULTY

Cakewalk

PREREQUISITES

None

PROBLEM

We are given a string S consisting of A ,B, C,D characters of length N. The substrings “ABC” and “BCD” are removed from the string wherever encountered. We have to determine whether the string is completely destroyed or not after any number of steps.

QUICK EXPLANATION

Count the frequency of each element A,B,C,D in the string. The string can be completely destroyed if and only if the frequency of element B equals the frequency of element C and sum of frequencies of elements A and D is equal to B or C.

EXPLANATION

We need not to be worried about the order of the corrupted substring as “ABC” and “BCA” are the same after rearrangement, and we can perform this operation any number of times.

Count the frequency of each character in the input string .

\rightarrow Meaning:

If the sequence of alphabets are correct after rearrangement then it can be removed from the string else it can’t be removed and hence, the string cannot be completely destroyed, so the answer for the test case will be NO.

Condition for completely destroyed string is

  • Number of element B = Number of element C

  • Number of element B = Number of element A + Number of element D

Example

\rightarrow Test case 3:

Consider the string “ABABCC”, before and after a valid move
Frequency of A = 2
Frequency of B = 2
Frequency of C = 2
Frequency of D = 0

As the frequency of element B = frequency of element C
Number of element B = Number of element A + Number of element D
Both the conditions are true , therefore we would get the desired output YES as the string is destroyed.

SOLUTIONS

Setter's Solution 
#include <iostream>
using namespace std;
int main()
{
    int t;
    cin >> t;
    for (int j = 0; j < t; j++)
    {
        int n;
        cin >> n;
        string s;
        cin >> s;
        int numOfA=0,numOfB=0,numOfC=0,numOfD=0;
        for(int i=0 ; i<n ; i++)
        {
            if(s[i]=='A')
            {
                numOfA++;
            }
            else if(s[i]=='B')
            {
                numOfB++;
            }
            else if(s[i]=='C')
            {
                numOfC++;
            }
            else if(s[i]=='D')
            {
                numOfD++;
            }
        }
        if((numOfA+numOfD)==numOfB && numOfB==numOfC)
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
    }
}
Editorialist's Solution 
 #include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
    string str;
    int n;
    cin>>n>>str;
    ll A = count(str.begin(),str.end(),'A');
    ll B = count(str.begin(),str.end(),'B');
    ll C = count(str.begin(),str.end(),'C');
    ll D = count(str.begin(),str.end(),'D');
    if(B!=C)
    {
        cout<<"NO\n";
        continue;
    }
    if(A+D==B)
    {cout<<"YES\n";}
    else{cout<<"NO\n";}
}

return 0;
}