ABCC3 - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: apoorv_me
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Prefix sums

PROBLEM:

You have a string S, containing only the characters a, b, and c.
In one move, you can choose a subsequence of S that equals 'abc', and delete either the a or the c from it.
Find the minimum possible number of operations that can be performed on S, so that it’s impossible to perform any more.

EXPLANATION:

The number of operations performed is equal to the number of characters deleted from S, so let’s look at it from that perspective, and find the minimum number of characters that must be deleted.

Clearly, every b in S will remain.
Suppose S_i = b. Then, for there to not be any 'abc' subsequence involving this b in the final string,

  • Every a that occurs before index i should be deleted, or
  • Every c that occurs after index i should be deleted.

Let the indices of b’s in S be b_1, b_2, \ldots, b_k in ascending order.
We’ll call index b_i an a-type if every a before it is deleted, and a c-type if every c after it is deleted (it’s never optimal for it to be both).

Observe that no matter how we perform operations, the set of a-type indices will form a prefix of [b_1, \ldots, b_k], and the c-types will form a suffix.
After all, if all the a’s before b_i are deleted, surely all the a’s before each of b_1, b_2, \ldots, b_{i-1} will also be deleted.

Let’s utilize this observation: for 0 \leq i \leq k, let’s fix the a-type indices to be b_1, \ldots, b_i, and try to find the minimum number of operations we need to do so.
For convenience, we define b_0 := 0 and b_{k+1} := N+1, which helps deal with border cases.
Observe that:

  • It’s enough to delete every a before index b_i: this automatically makes all of b_1, b_2, \ldots, b_i be a-types.
  • The indices \gt b_i should be c-types.
    For this, it’s similarly enough to delete every c after index b_{i+1}.
  • So, the number of moves required equals the number of a’s before b_i, plus the number of c’s after b_{i+1}.
    Both these quantities can be found in \mathcal{O}(1) time with the help of prefix/suffix sums.

We now have a lower bound on the answer: take the minimum number of operations across all k+1 choices of i above.
It’s not hard to see that operations can be performed in such a way that we reach this bound too, which thus makes it the answer.

Proof

In an optimal solution, suppose we want to make b_1, \ldots, b_i into a-type indices, and b_{i+1}, \ldots, b_k into c-type indices.
If multiple i attain the minimum, choose the largest one among them.

Now, if there exists an occurrence of c after index b_i, we can use that occurrence to delete every a before b_i. Then,

  • If i = k, we’re done since there are no occurrences of c to the right of b_{k+1} = N+1.
  • Otherwise, since we chose the largest optimal index, there must be an a between indices b_i and b_{i+1} - otherwise, b_{i+1} would also be optimal (and we know it isn’t).
    So, using this a, every c after b_{i+1} can be deleted.

This leaves only the case of when there are no c’s after index b_i.
Here,

  • If S itself contains no c’s, then the answer is 0 anyway.
  • Otherwise, let the last c in S be between indices b_j and b_{j+1}. Note that j \lt i.
    Further, it’s still optimal to choose b_j instead of b_i, since either way no c’s must be deleted and instead we may delete less a’s.
    Choosing b_j now gives us an occurrence of c to the right to work with, and so we’re done.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

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

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int sumN = 0;
    auto __solve_testcase = [&](int test) {
        int N; cin >> N;
        string S; cin >> S;
        S = "bb" + S + "bb"; N += 4;
        vector<int> ind, pfa(N + 1), pfc(N + 1);
        for (int i = 0 ; i < N ; ++i) {
            if(S[i] == 'b')		ind.push_back(i);
            pfa[i + 1] = pfa[i] + (S[i] == 'a');
            pfc[i + 1] = pfc[i] + (S[i] == 'c');
        }
        int ans = N;
        for(int i = 0 ; i + 1 < (int)ind.size() ; ++i) {
            ans = min(ans, pfa[ind[i]] + pfc[N] - pfc[ind[i + 1]]);
        }
        cout << ans << '\n';
    };
    
    int NumTest = 1;
    cin >> NumTest;
    for(int testno = 1; testno <= NumTest ; ++testno) {
        __solve_testcase(testno);
    }

    assert(sumN <= (int)3e5);
    
    return 0;
}
Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    s = 'b' + input() + 'b'
    n += 2
    
    b = []
    for i in range(n):
        if s[i] == 'b': b.append(i)
    prefa = [0]*n
    sufc = [0]*n
    for i in range(n):
        if s[i] == 'a': prefa[i] = 1
        if i > 0: prefa[i] += prefa[i-1]
    for i in reversed(range(n)):
        if s[i] == 'c': sufc[i] = 1
        if i+1 < n: sufc[i] += sufc[i+1]
    
    ans = n
    for i in range(len(b)-1):
        x, y = b[i], b[i+1]
        ans = min(ans, prefa[x] + sufc[y])
    print(ans)
1 Like
2

Can anybody help me figure out what is the problem in my solution ?

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;

        vector<long long> prefixA(n, 0), suffixC(n, 0);
        if(s[0] == 'a') prefixA[0] = 1;
        if(s[n-1] == 'c') suffixC[n-1] = 1;

        for(int i = 1; i < n; i++) {
            prefixA[i] = (s[i] == 'a') ? prefixA[i-1] + 1 : prefixA[i-1];
            suffixC[n-i-1] = (s[n-i-1] == 'c') ? suffixC[n-i] + 1 : suffixC[n-i];
        }

        long long ans = n;
        int che = 0;
        for(int i = 0; i < n; i++) {
            if(s[i] == 'b' && prefixA[i]!=0 && suffixC[i]!=0) {
                che = 1;
                ans = min(ans, prefixA[i] + suffixC[i]);
            }
        }
        if (che==0){
          cout<<0<<endl;
          continue;
        }else{
        for (int i = 0; i < n; i++)
        {
          if (s[i]=='b' && prefixA[i]!=0 && suffixC[i]!=0){
            ans = min(ans, suffixC[i]);
            break;
          }
        }
        for (int j = n-1; j >=0; j--)
        {
           if (s[j]=='b'  && prefixA[j]!=0 && suffixC[j]!=0){
            ans = min(ans, prefixA[j]);
            break;
           }
        }
        
        cout << ans << "\n";}
    }

    return 0;
}
3

Your solution fails on

1
8
abaaccbc

The answer is 2.

It looks like you’re considering only a single 'b' at a time and looking at a’s to its left and c’s to its right, but you can do better than that by considering two adjacent b’s.

2 Likes
4

void solve() {
int n = 0;
cin >> n;
string s;
cin >> s;
int mina = -1 , maxc = -1;
int cnta = 0 , cntcn = 0;
for (int i = 0; i < n; i++) {
if (s[i] == ‘a’) {
mina = i;
break;
}
}
for (int i = n - 1; i >= 0; i–) {
if (s[i] == ‘c’) {
maxc = i;
break;
}
}
if (mina == -1 || maxc == -1 || mina > maxc) {
cout << 0 << nline;
return;
}
vector cntc(n + 1 , 0);
for (int i = n - 1; i >= 0; i–) {
cntc[i] = cntc[i + 1] + (s[i] == ‘c’);
if (s[i] == ‘a’) cnta++;
else if (s[i] == ‘c’) cntcn++;
}
vector prefa(n + 1 , 0);
for (int i = 0; i < n; i++) {
prefa[i + 1] = prefa[i] + (s[i] == ‘a’);
}
int oper = min(cnta , cntcn);
int j = mina;
int dele = 0;
debug(mina);
debug(maxc);
debug(cntc)
for (int i = mina; i <= maxc; i++) {
// delete a’s upto i…
if (s[i] != ‘a’) continue;
j = max(j , i);
debug(i);
debug(j);
while (j <= maxc && s[j] != ‘b’) {
j++;
}
if (j > maxc) {
oper = min(oper , dele);
}
else oper = min(oper , dele + cntc[j + 1]);
dele++;
debug(oper)
}
cout << oper << nline;
}

In this I am trying to use the fact that in optimal solution some a’s from starting will be deleted and some c’s from ending to a particular index will be deleted … so we can fix upto which a’s will be deleted and calculate how much minimum c’s will need to be deleted when we delete upto a fixed index of ‘a’ … and calculate the minimum over all the a’s …

5

Please help me to figure out what’s wrong with my solution. My idea is quite simple. I first stored the indices of c. Then I iterated through the string and keep the count of a’s. Then when I encountered a ‘b’, I check the number of a’s and the size of ‘c’ queue and stores the min.

include <bits/stdc++.h>
using namespace std;
define ll long long
int main() {
// your code goes here
int nt;
cin>>nt;
while(nt–){
long long int n;
string s;
cin>>n>>s;
long long int ans=0,counta=0;
queuec;
for(int i=0;i<n;i++){
if(s[i]==‘c’)c.push(i);
}
for(int i=0;i<n;i++){
if(c.front()==i)c.pop();
if(c.empty())break;
if(s[i]==‘a’)counta++;
else if(counta and (int)c.size() and s[i]==‘b’){
int size=c.size();
if(counta<c.size()){
ans+=counta;
counta=0;
}else{
ans+=c.size();
while(!c.empty())c.pop();
break;
}
}
}
cout<<ans<<endl;
}
return 0;
}