I am unable to use Tex for some reason and will format the blog later.

Problem A. Sherlock and Parentheses

Category: Ad-Hoc, Math, Greedy

Let's define n = min(L,R). Then the claim is that the sequence "()()...()" consisting of n pairs of "()" will give us the maximum answer.

Proof:

Let's look at some sequence T = (S) where S is also a balanced parenthesis sequence of length m. Let's denote by X(S), the number of sub-strings of S that are also balanced and by X'(S) the number of balanced parenthesis sub-strings that include the first and last characters of S (In fact this will be just 1). Then X(T) = X(S) + X'(S).

It should be easy to prove that X'(S) <= X(S) (simply because X'(S) is a constrained version of X(S))

If we rearrange our sequence T to make another sequence T' = "S()", then X(T') >= X(S) + X'(S). The greater than equal to sign comes because we might have balanced sub-strings consisting of a suffix of S and the final pair of brackets.

Since X(S) >= X'(S), we have that X(T') >= X(S) + X'(S) = X(T). Thus by rearranging the sequence in this manner, we will never perform worse. If we keep applying this operation on each string, we will finally end up with a sequence of the form "()()...()" possibly followed by non-zero number of "(" or ")"