Codeforces 1167D. Bicolored RBS Educational Codeforces Round 65

Problem link

Let d(s) be nested depth of RBS s. There is an interesting fact that max(d(r),d(b))≥⌈d(s)/2⌉. From the other side we can always reach equation max(d(r),d(b))=⌈d(s)/2⌉ using some approaches.

Let's look at prefix of length i of string s. Let os(i) be number of opening bracket in the prefix, cs(i) — number of closing brackets. Then we can define balance of the i-th prefix of s as bals(i)=os(i)−cs(i).

The author's approach is next:

Let's define level of pair of brackets (matched in natural way) as bals(i−1), where i is position of opening bracket of this pair. Then we will color in red all pairs with even level and in blue — with odd level.

—— Proof of max(d(r),d(b))≥⌈d(s)/2⌉:

It can be shown that d(s)=max1≤i≤n(bals(i)) and exists such pos that d(s)=bals(pos).

After any coloring of s we can define number of opening/closing red (blue) brackets of pos-th prefix of s as or(pos) (ob(pos)) and cr(pos) (cb(pos)) respectively. Since os(pos)=or(pos)+ob(pos) and cs(pos)=cr(pos)+cb(pos), then
max(balr(pos),balb(pos))=max(or(pos)−cr(pos),balb(pos))=max((os(pos)−ob(pos))−(cs(pos)−cb(pos)),balb(pos))=max((os(pos)−cs(pos))−(ob(pos)−cb(pos)),balb(pos))=max(bals(pos)−balb(pos),balb(pos))≥⌈bals(pos)/2⌉=⌈d(s)/2⌉.
Finally,
max(d(a),d(b))=max(max1≤i≤n(balr(i)),max1≤i≤n(balb(i)))=max1≤i,j≤n(max(balr(i),balb(j)))≥max(balr(pos),balb(pos))≥⌈d(s)/2⌉

A solution in c++