SRM 714, D2, 500-Pointer (RemovingParenthesis)

James S. Plank

Wed May 10 01:36:53 EDT 2017

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: May, 2017
Competitors who opened the problem: 286
Competitors who submitted a solution: 153
Number of correct solutions: 114
Accuracy (percentage correct vs those who opened): 39.9%
Average Correct Time: 32 minutes, 7 seconds.

This problem screams dynamic programming, and the constraints are so small, that you don't really need to be too creative. To wit:

The obvious base case is the empty string. There's one way to get this string.
For the recursion, try every letter from s[1] to s[s.size()-1]. If you remove the first character and this character, and you are left with a legal string, then call countWays() recursively, and add this to the solution.
Return your solution.

So, loop i from 1 to s.size()-1, and create a new string composed of the characters from 1 to i-1 and from i+1 to the end of the string. Test this for legality. If it's legal, call countWays() recursively on it, and add the return value to a running sum of return values. When you're done with the loop, return the total. Of course, this is a dynamic program, so you should memoize.

Let's use example 0 from the writeup to illustrate. The string is:

( ) ( ) ( ) ( ) ( )

Now, we'll run through all of the characters, starting with s[1], and if the character is a right paren, then we build a new string where we delete s[0] and the right paren, test for legality, and if legal, make the recursive call. Let's use the following table to see the strings and recursive calls:

i	String with deleted characters in orange	Legal and do recursion?
1	`( ) ( ) ( ) ( ) ( )`	Yes
3	`( ) ( ) ( ) ( ) ( )`	No
5	`( ) ( ) ( ) ( ) ( )`	No
7	`( ) ( ) ( ) ( ) ( )`	No
9	`( ) ( ) ( ) ( ) ( )`	No

It should be pretty clear that this one's answer is going to be one. Let's try example 2 to show one with more recursion. Here's the string:

( ( ( ) ( ) ( ) ) )

And here's the table:

i	String with deleted characters	Legal and do recursion?
3	`( ( ( ) ( ) ( ) ) )`	Yes
5	`( ( ( ) ( ) ( ) ) )`	Yes
7	`( ( ( ) ( ) ( ) ) )`	Yes
8	`( ( ( ) ( ) ( ) ) )`	Yes
9	`( ( ( ) ( ) ( ) ) )`	Yes

If you still need some more detail, here's example two run to completion -- for each string, I'll print the recursive calls that it makes, and the final values:

s:         ()  Returns  1   Calls: :1
s:       (())  Returns  2   Calls: ():1 ():1
s:     ((()))  Returns  6   Calls: (()):2 (()):2 (()):2
s:       ()()  Returns  1   Calls: ():1
s:     (()())  Returns  4   Calls: (()):2 ()():1 ()():1
s:   ((()()))  Returns 18   Calls: ((())):6 (()()):4 (()()):4 (()()):4
s:     ()(())  Returns  2   Calls: (()):2
s:   (()(()))  Returns 12   Calls: ((())):6 ()(()):2 ()(()):2 ()(()):2
s:     ()()()  Returns  1   Calls: ()():1
s:   (()()())  Returns  8   Calls: (()()):4 ()(()):2 ()()():1 ()()():1
s: ((()()()))  Returns 54   Calls: ((()())):18 (()(())):12 (()()()):8 (()()()):8 (()()()):8

If running time were an issue, there are many things you could do. One of the fun ones would be to turn the string into a linked list, because that way, "deleting" a character would be more efficient. However, nothing like that is necessary -- you can solve this by constructing the new string on the fly.

Commented solution in Solution.cpp.

/* Topcoder SRM 714, D2, 500-pointer.
   RemovingParenthesis
   James S. Plank
   Mon May 15 15:56:16 EDT 2017
 */

#include <string>
#include <map>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

class RemovingParenthesis
{
    public:
        int countWays(string s);
        map <string, int> C;
};

int RemovingParenthesis::countWays(string s)
{
    int i, j;
    int legal;     // Is the new string legal?
    int level;     // Use this to keep track of nesting level when testing for legality.
    int total;     // Sum of all recursive calls.
    string s2;     // The string that we build from deleting characters 0 and i.

    /* Base case -- return 1 for the empty string. */

    if (s.size() == 0) return 1;

    /* Check the cache to see if you've solved this one already. */

    if (C.find(s) != C.end()) return C[s];

    total = 0;

    /* Run through each character starting with i=1.
       If the character is a right paren, then construct
       s2 by deleting characters 0 and i.  Use substr()
       to do this. */

    for (i = 1; i < s.size(); i++) {

        if (s[i] == ')') {
            s2 = (s.substr(1, i-1) + s.substr(i+1));

            /* Now test s2 for legality */

            legal = 1;
            level = 0;

            for (j = 0; j < s2.size(); j++) {

                if (s2[j] == '(') {
                    level++;
                } else {
                    level--;
                }

                if (level < 0) legal = 0;
            }

            /* The constraints guarantee that level will = 0
               at the end of the loop above.  If they didn't,
               I should make sure that level equals 0 here. */

            /* If it's legal, then make the recursive call. */

            if (legal) total += countWays(s2);
        }
    }

    /* Memoize and return at the end. */

    C[s] = total;
    return total;
}