1
$\begingroup$

I'm trying prove the correctness of my algorithm.
This is the problem in codeforces: https://codeforces.com/contest/1428/problem/C

Here's my code in C++ which was accepted:

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
 
using namespace std;
 
int main()
{
    int num, ans, top;
    string s;
 
    cin >> num;
 
    for (int i = 0; i < num; i++)
    {
        cin >> s;
 
        ans = s.size();
 
        top = 0; // meaning no characters behind
 
        for (int j = 0; j < s.size(); j++)
        {
            if (top == 0) top++;
            else if (s[j] == 'A') top++;
            else { ans -= 2; top--; }
        }
 
        cout << ans << endl;
    }
    return 0;
}

It's easy to see that if the string still contains B as the "middle character", we can always make more deletions. And in order to make this string as short as possible, we will always try to delete B with an A(So, we still have more B(s) to continue the delete process).

So, the idea to solve this problem is simple: While tracing through the string, we have a variable called top which "collects" all the A(s) and the first character of the string(the original one or the string after some deletion when top = 0). And whenever we encounter a B, it's always nice if we have collected at least one A(top >= 2) or we have to reluctantly erase this B with the first character of the string without knowing whether it's an A or B.

An algorithm correctly solves this problem if and only if:

  1. It delete all middle B(s)
  2. It makes the string as short as possible

But how do we prove the correctness of this algorithm? Clearly, my algorithm does the "right thing" when top >= 2. But when top = 1, how do I prove that the behavior of erasing B with the first character of the string without knowing whether it's an A or B is correct?

My further reasoning goes like this:
In other words, are there any other algorithms that erase the same amount of AB(s) without confronting this reluctance?

Here's what I've tried to come up with:

We only consider the case when the "real reluctance" happens. What I mean is when the first character of the string is B.

So let's say, there was such "better" and correct algorithm(call it X). In other words:

  1. X erases all AB(s) that our old algorithm erases.
  2. There exists moments when our old algorithm encounters a "real reluctance" but X finds an AB to erase.

Question: The thing is where do all those AB(s) lie ?

(First character A)A...A B A...A B ... B*(characters of the original string)
-------------------^----------------^
-------------------|----bound Y----|

B* is where the reluctance happens.

What has to be pointed out first is that according to condition 1, X is not allowed to erase a B outside bound Y with an A inside bound Y. Because otherwise, there exists some B inside bound Y that can't be erased which proves X a wrong algorithm. (*)

Returning to our question, if for every such moment, AB lies entirely inside bound Y, then our old algorithm erases all the AB(s) that X does. So, X can not be better.

So, there exists a moment where AB lies outside Y and statisfies (*). But this AB will, surely, soon be erased by our algorithm(this can be easily imagined and proved).

B*...A...B...(this A will collected by top and will be matched with the latter B).
So, X can not be better.

Therefore, our algorithm is correct. There're no other algorithms that will make the string shorter.

$\endgroup$
2

1 Answer 1

1
$\begingroup$

An easy-to-see algorithm that is potentially much simpler than yours but runs on the same idea is just to simply remove all "AB" pairs first, then remove all "BB" pairs.

As you observed, we must have a B in the center of our string in order to keep making it shorter -- and to keep the most B's in the center as opposed to just erasing them all, we erase all of the "AB" pairs first. We can also observe that removing a "BB" pair before an "AB" pair can cause us to return the wrong answer (ex. "AAABB" -> "AAA" instead of "A") but removing an "AB" pair before a "BB" pair cannot increase out answer, as for every optimal solution that removes a "BB" pair in the center (with at least one A before it) we can create another optimal solution by simply removing the "AB" instead of the "BB".

That being said, your solution does work for when top = 1, as, if it's an "AB" pair, it obviously should be removed in accordance to the above statement, and if it's a "BB" pair, there will be no "AB" pairs before it to remove in order to create another optimal solution (as there are no A's before it), thus removing the "BB" must be part of the optimal solution.

My solution that also got accepted:

#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <chrono>
 
using namespace std;

void remove_substr(string& s, string t) {
    for (int i {}; i < (int)s.size()-1;)
        if (s.substr(i, 2) == t) {
            s.erase(i, 2);
            if (i != 0) i--;
        } else i++;
}
 
int main() {
    int t; cin >> t;
    while (t--) {
        string s; cin >> s;
        remove_substr(s, "AB");
        remove_substr(s, "BB");
        cout << s.size() << "\n";
    }
    return 0;
}
$\endgroup$
3
  • 1
    $\begingroup$ Simpler is a matter of perspective. One approach manipulates strings for the better part, the other one counts. $\endgroup$
    – greybeard
    Dec 26, 2021 at 21:37
  • $\begingroup$ Thank you! The proof of correctness for your algorithm is much simpler than mine - we just have to prove the two algorithms are equivalent, which is not hard to see! $\endgroup$ Dec 27, 2021 at 1:35
  • $\begingroup$ The difference is that the two algorithms delete AB(s) and BB(s) in different orders. Your algorithm delete AB(s) then BB(s). My algorithm deletes in place. That is, after it deletes all the AB(s) that go before their closest BB to the right. And then, it does not leave that BB there but immediately deletes it! $\endgroup$ Dec 27, 2021 at 1:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.