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

Question

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.

Your task is to determine if such a string b exists.

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.

Answer 1

Yes, your algorithm is correct.

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.

Answer 2

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.