Prove my algorithm that solves ABC String problem in Codeforces is correct

Here's the statements of problem A, "ABC String" in Educational Codeforces Round 105 (Rated for Div. 2)

You are given a string a, consisting of n characters, n is even. For each i from 1 to n $$a_i$$ is one of 'A', 'B' or 'C'.

A bracket sequence is a string containing only characters "(" and ")". A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence. For example, bracket sequences "()()" and "(())" are regular (the resulting expressions are: "(1)+(1)" and "((1+1)+1)"), and ")(", "(" and ")" are not.

You want to find a string b that consists of n characters such that:

b is a regular bracket sequence; if for some i and j $$(1≤i,j≤n1≤i,j≤n) a_i=a_j$$, then $$b_i=b_j$$. In other words, you want to replace all occurrences of 'A' with the same type of bracket, then all occurrences of 'B' with the same type of bracket and all occurrences of 'C' with the same type of bracket.

I submitted my code and it's accepted.

The idea is brute-force. There're only $$2^3 - 2$$ cases for $$A, B, C$$ to consider, since $$A, B, C$$ cannot be all "(" nor all ")", because a RBS(regular bracket sequence) must contain at least one "(" and one ")".

So the problem is to check for validity of each case. What's the algorithm for that?

The idea is to keep track of the number of close brackets and open brackets so that these two conditions hold throughout the search from left to right:

1. $$cnt_{close} \leq cnt_{open}$$
2. At the end of the search, $$cnt_{close} = cnt_{open}$$

cnt stands for counter.

But does this algorithm actually work? We have to prove that a BS is considered RBS if and only if the two above conditions hold throughout the search from left to right.

The first side is easy to prove. If a BS is a RBS, we clearly must have $$cnt_{close} = cnt_{open}$$ at the end of the loop.

And we can't have $$cnt_{close} > cnt_{open}$$ at any point of the search since if we've found a redundant close bracket, it cannot match with any open bracket before it. However, for every close and open brackets in a RBS, it always has a partner. So the two theories are contrary.

Therefore, the two conditions must hold when a BS is a RBS.

The reverse side is more tricky. I'm wrapping my head around it. I tried induction on the second condition and the reductio method but nothing works out.

My reductio approach: So let's assume that when the two conditions hold, we do not have a RBS which means only two cases happen: Either we have $$cnt_{close} \neq cnt_{open}$$ at the end of the loop or a pair of "(" and ")" follow the wrong order, namely "...(1)... ) ...(2)...( ...(3)...".

The former can't happen due to the second condition.

While searching throughout "area (1)", we cannot have $$cnt_{close} \geq cnt_{open}$$ since that would fail the first condition.
That's how far I've gone. Nothing more. I'd like to hear from you your approach to this problem. Thank you in advance!

25/11/2021: What if we define a "RBS" to be a BS such that:

1. For every close bracket, it has a unique partner from the left.
2. The number of open brackets equal to the number of close brackets.
• The definition at the end is interesting. However, what is "a partner from the left" for a closing bracket? When is there no partner or several partners? Yes, I know what you mean probably. What I mean is, there are easier and clearer definitions. Nov 25 '21 at 17:58

As you have experienced, the fundamental difficulty in proving your algorithm is correct is the definition of "regular bracket sequence". Even a student in early primary schools may understand the definition given in the Codeforces problem, "a regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters '1' and '+' between the original characters of the sequence." However, that definition does not mention explicitly what is required of brackets in a correct arithmetic expression. While it is clear what is a "correct arithmetic expression" intuitively, the intuition becomes illusive when you need to prove the correctness rigorously.

Here is a formal definition of "a regular bracket sequence" or "a string of balanced brackets".

Given word $$u$$ that consists of "$$($$" and "$$)$$", let $$D(u)$$ be the number of occurrences of the left parentheses in $$u$$ minus the number of occurrences of the right parentheses in $$u$$. Such a word is said to be word of well-balanced parentheses (or "a regular bracket sequence") if

1. $$D(u) = 0$$ , and
2. $$D(v) \ge 0$$ for any prefix $$v$$ of $$u$$.

If the definition above is used, then, of course, your algorithm is correct!

Here is another formal definition of "a regular bracket sequence" or "a string of balanced brackets".

A word $$u$$ that consists of "$$($$" and "$$)$$" is a word of well-balanced brackets (or "a regular bracket sequence") if

1. $$u$$ is empty, or
2. $$u=(u_1)$$ for some well-balanced brackets $$u_1$$, or
3. $$u=u_1u_2$$ for some well-balanced brackets $$u_1$$ and some well-balanced brackets $$u_2$$.

Welcome to the world of Dyck language!

Exercise. Prove the two definitions above are equivalent to each other.

• In order to be consistent with Codeforces, a "bracket" in this answer means either "$($", an opening bracket or "$)$", a closing bracket. Nov 25 '21 at 17:51
• Here is another recursive definition. A string $u$ that consists of "$($" and "$)$" is a regular bracket sequence if it is either empty or it becomes a regular bracket sequence after deleting a substring that is "$()$". Nov 25 '21 at 18:26
• Thanks. You just simplify a whole mess in my mind :D. I also noticed that if I use my written definition(or your simplified version), the problem is trivial but it seems somewhat informal. Your second definition is exactly what I've been pursuing but it's quite tough going from there. Maybe I'll post my unfinished proof. I hope you can spend some time helping me finish it :D. Thank you, by the way. Nov 26 '21 at 0:28
• I've written the proof. If you have time, please have a look at it : D Nov 26 '21 at 4:08

I'll write the proof for: If a regular bracket sequence follows the second definition, it is true that it has the property stated in the first definition.

A word $$u$$ that consists of "$$($$" and "$$)$$" is a word of well-balanced brackets (or "a regular bracket sequence") if

1. $$u$$ is empty, or
2. $$u=(u_1)$$ for some well-balanced brackets $$u_1$$, or
3. $$u=u_1u_2$$ for some well-balanced brackets $$u_1$$ and some well-balanced brackets $$u_2$$.

Let us view these 3 conditions as functions that return a string.

$$\forall u$$ as a RBS, $$1(u)$$ returns an empty string(let's denote it $$\emptyset$$)
$$\forall u$$ as a RBS, $$2(u)$$ returns ($$u$$)
$$\forall u$$ and $$v$$ as two RBS(s), $$3(u,v) = uv$$

So, all RBS will just be a result of a composite function which is made from these three functions.

For example:
"()()()" = $$3(3(2(\emptyset), 2(\emptyset) ), 2(\emptyset))$$

Let's denote $$len(u)$$ to be the length of a string $$u$$

Lemma 1: The number of brackets in a RBS is even.

Proof: Consider a RBS $$u$$.
We'll use induction. It is true that "(" or ")" cannot be formed.

Assume the theory is true for every odd number less than $$n$$($$n$$ is odd and $$n\geq 1$$). We'll disprove a RBS $$u$$ of length $$n+2$$.

Case 1: $$u = 2(v)$$. RBS $$v$$ has length of $$n$$, which is absurd.

Case 2: $$u = 3(a, b)$$ with $$a$$ and $$b$$ both not an empty string and both RBS(s). $$len(u) = len(a) + len(b)$$. Since (n+2) is odd, we must have $$len(a)$$ or $$len(b)$$ is odd. Again, this is absurd.

Lemma 2: Every RBS $$u$$, which is not an empty string, starts with "(".

Proof: Let us use induction on length $$n$$ of $$u$$. We start with $$n = 2$$. The only possibility is "()". This one starts with "("

Assume the theory is true for every even $$n \geq 2$$. We prove it is also true for $$n+2$$

Since $$u$$ is not an empty string, we have:
$$u = 2(v)$$, which proves the lemma.
Or: $$u = 3(a,b)$$ with $$a$$ and $$b$$ not both empty strings. $$len(a) < n$$. So, $$a$$ starts with "(". We're done.

Lemma 3: The number of open brackets equal to the number of close brackets.
Proof:

Induction again. Empty string is the base case. Let us assume correctness for every $$n \geq 0$$.

Case 1: $$u = 2(v)$$. $$D(v) = 0$$. So, adding one close bracket and one open bracket affects nothing.
Case 2: $$u = 3(a,b)$$. $$D(u) = D(a) + D(b) = 0$$. We're done.

Lemma 4: For every prefix $$v$$ of $$u$$, we have $$D(u) \geq 0$$.
Proof:
Assume the reverse. We have $$D(u) < 0$$ for some prefix $$v$$.

For example: $$u = (( )))))...$$

We'll prove this is ridiculous. Let's denote the number of open brackets as $$cnt_{open}$$ and the number of close brackets as $$cnt_{close}$$. So, $$cnt_{open} < cnt_{close}$$.

Case 1: $$u = 3(a, b)$$. The only possibility for $$a$$ is (()). Since if we pick further than that, $$a$$ won't be a RBS due to Lemma 3. But then $$b$$ will starts with ")", which is absurd.

So $$u = 2(v_1)$$. $$v_1$$ is just $$u$$ with $$cnt_{close} - 1$$ and $$cnt_{open} - 1$$. Again, $$D(v) < 0$$.

The process repeats. We must have $$v = 2(v_2)$$ for some $$v_2$$. Consider $$v_{cnt_{open}}$$. This one starts with ")", which is absurd. We're done!

Lemma 3 and Lemma 4 proves the initial problem.

• @JohnL. What do you think, John? Nov 26 '21 at 4:04
• Pretty good. If you just want to prove that what is defined by the second definition satisfies the two properties in the first definition, a slightly shorter proof might be clearer. Nov 26 '21 at 4:09
• Thanks. "You can prove more directly" is interesting. It'd be kind if you could provide an answer to your exercise. :D Nov 26 '21 at 4:14
• You could study this page that explains the definitions and properties of well-balanced words on several types of parentheses. Nov 26 '21 at 4:32