June 21, 2018 Problem of the Week: Removing Parentheses

This week, we’ll discuss a problem that first appeared in the 2017 TCO Russia Regionals Round. The problem was set by lg5293 and the problem summary is as follows –
Correct parentheses sequences can be defined recursively as follows:

    The empty string "" is a correct sequence.
    If "X" and "Y" are correct sequences, then "XY" (the concatenation of X and Y) is a correct sequence.
    If "X" is a correct sequence, then "(X)" is a correct sequence.
    Each correct parentheses sequence can be derived using the above rules.

Examples of correct parentheses sequences include “”, “()”, “()()()”, “(()())”, and “(((())))”.
Now, the problem is – Given a perfect parentheses string, and given you start pairing the leftmost open parentheses with any closed parentheses to its right and removing this pair, how many ways are there to obtain a null/empty string, while ensuring that all intermediate strings formed are also perfect.
For example – The string “(())” has 2 ways of being broken down – The first open parentheses may be combined with EITHER the first or second closing parentheses, and the second open parentheses will be forced to take the other closing parentheses.
The string “()()()” has only one way of being broken down – Every open parentheses HAS to be paired with the corresponding closing parentheses that immediately follows, or else the intermediate string will not be perfect.
The answer to this may seem tricky at first glance, but leveraging a known fact the problem statement has guaranteed us with, allows us to solve this easily.
The “known fact” is that the initial input string is already perfect.
This means that for every open parentheses, there is guaranteed to be a closing parentheses.
Let us consider a proof.
In all perfect strings, for every prefix, the number of open parentheses will be greater than or equal to the number of closed parentheses.
So, if I have encountered X open parentheses, my first encounter with a close parentheses allows me to pair this closed parentheses with any of the X open parentheses, as doing so will make me remove a valid pair.
For example – “((( )…”
The dots represent a larger string which is irrelevant at the moment. In the above string, as 3 open parentheses were encountered before finding a closing parentheses, it is valid to pair the closing parentheses with any of the 3 open parentheses.
At this point, our answer multiplies by the number of choices we have, therefore it is multiplied by the number of open parentheses currently encountered.
After pairing, its important to decrement the number of open parentheses encountered as one of them was just used to complete the previous pairing.
The algorithm’s pseudocode is as follows –

    ct = 0
    ans = 1
    Start from the leftmost character{
         if (current character == ' ( ' )
              ct = ct + 1
         else{
              ans = ans * ct
              ct = ct - 1
         }
    }
    print ans

Consider another example – “( ) ( ( ) ( ) )” –
Spaces have been added for easier reading.
Now, lets label the parentheses in order of appearance – A, B, C, D, E, F, G, H
Parentheses A can only be paired with B.
Encounter C and D, and increment the counter.
Upon encountering E, counter equals 2 (having encountered C and D). Therefore 2 possibilities arise – Either C pairing with E or D pairing with E. Answer is now 2.
Assume either, and decrement counter for the number of free open parentheses have decreased by one.
Encounter F, increment counter.
Encounter G, multiply answer by 2, decrement counter by 1. Answer is now 4.
Encounter H, multiply answer by 1, decrement counter by 1.
Therefore, the final answer is 4, and the pairings are as follows –
1. AB, CE, DG, FH
2. AB, CE, FG, DH
3. AB, DE, CG, FH
4. AB, DE, FG, CH
Because the input is guaranteed to be perfect, we can show that we may pair any closed parentheses with any open parentheses occurring before it that is available.
And thus, the problem can be solved. The implementation has been left as an exercise for the reader.
Additionally, the best solution in terms of time were by tourist, taking him 1 minute and 51 seconds and his implementation is available here – https://community.topcoder.com/stat?c=problem_solution&cr=22263204&rd=16916&pm=14595