### James S. Plank

Mon Oct 10 23:52:16 EDT 2016

In case Topcoder's servers are not running correctly, here is a summary of the problem:
• A "correct" bracket sequence is a properly nested and/or contatenated sequnce of () and [] bracket combinations.
• So, () and [] are correct bracket sequences.
• If X is a correct bracket sequences, then (X) and [X] are also correct bracket sequences.
• The empty string is not a correct bracket sequence.
• If X and Y are correct bracket sequences, then XY is a correct sequence.
• Let s be a correct bracket sequence between 1 and 40 characters in size.
• Let S be a subset of the indices of s.
• How many S subsets are there, so that if you delete the indices in S from s, the result is a correct bracket sequence.

This is a pretty classic topcoder dynamic programming problem. As always, the challenge is spotting the recursion.

### Solving it inefficiently so we can test answers

Before we solve this correctly, though, let's solve it inefficiently. This will let us test our solution for correctness, even if it won't solve big problems.

The inefficient solution is to use a power set enumeration, straight out of the CS302 lecture notes. I've written this up in BSPS.cpp. Obviously, this will start to choke when the string's size is in the 20's. But again, it lets us test our answers:

 ```/* Test to see if a string s is a correct bracket sequence. Use a deque like a stack -- if a character is an opening character, push it on the stack. If it is a closing character, check to see its opening character is on the stack. If so, pop it and continue. Otherwise, return false. */ int is_cbs(string &s) { deque stack; int i; for (i = 0; i < s.size(); i++) { if (s[i] == '(' || s[i] == '[') { stack.push_front(s[i]); } else if (s[i] == ')' || s[i] == ']') { if (stack.empty() || (s[i] == ')' && stack[0] != '(') || (s[i] == ']' && stack[0] != '[')) return 0; stack.pop_front(); } else return 0; } return stack.empty(); } int main(int argc, char **argv) { string s, tmp; int i, j, counter; if (argc != 2) { fprintf(stderr, "Usage a.out string\n"); exit(1); } s = argv[1]; counter = 0; /* Generate all non-empty subsets of S and test them. Count up the results. */ for (i = 1; i < (1 << s.size()); i++) { tmp = ""; for (j = 0; j < s.size(); j++) { if (i & (1 << j)) tmp.push_back(s[j]); } if (is_cbs(tmp)) counter++; } printf("%d\n", counter-1); exit(0); } ```

### Doing a better job

Let's use an example that's not in the writeup:
```s = "[(])][]"
```
Let's enumerate the solutions -- there are 11.
• Delete characters 0 through 4 to get []
• Delete characters 0, 2 and 4 to get ()[]
• Delete characters 0, 2, 4, 5 and 6 to get ()
• Delete characters 1, 3 and 4 to get [][]
• Delete characters 1, 3, 4, 5 and 6 to get []
• Delete characters 1, 2 and 3 to get [][]
• Delete characters 1, 2, 3, 5 and 6 to get []
• Delete character 2 to get [()][]
• Delete characters 2, 5 and 6 to get [()]
• Delete characters 1, 2, 3, 4 and 5 to get []
• Delete characters 3, 4 and 6 to get ()[]

In this problem, as with many dynamic programming problems, it's best to work from left to right, concentrating on the first character of the string. So, in the case of our example, we are going to concentrate on the first character -- the left square brace:

```[(])][]
```
The number of ways to erase characters and get valid bracketed strings is going to be the number of ways that you can do it by erasing the first character, plus the number of ways that you can do it by not erasing the first character. If we erase the first character, than we can simply call count() on the remaining characters, and that will be our answer. In the example above, we'd call:
```count("(])][]");
```
That's nice. Now, when we don't erase the first character, we need to do something so that we can recurse on smaller strings. Let's match the first with its nearest closing square bracket. We get the following (and I'm coloring the strings for clarity):
```[(])][]
```
The number of ways to erase characters and get correct bracket sequences, when you are not erasing the red characters, will be the number of ways for:
```[(]
```
when you don't delete the red characters, multiplied by
```)][]
```
when you are allowed to delete any and all characters. This turns out to be:
```count("(")+1
```
multiplied by:
```count(")][]")+1
```
Why the +1's? Because we want to count empty strings in these instances, and count() does not include the empty string. So you add one. It is important to realize that because you are not deleting the red characters, it's ok for the other strings to become empty, and that's why you add one to the recursive count() calls.

Next, you match the first character with the next closing square brace:

```[(])][]
```
And you do the same thing -- it equals
```(count("(])")+1)*(count("[]")+1)
```
Finally, you match the first character with the last closing square brace:
```[(])[]
```
And you do the same thing -- it equals
```(count("(])][")+1)*(count("")+1)
```
Add them up, and you're done. Let's work through the numbers in our example:
• Deleting the first character = count("(])][]"). This is 3.
• Retaining the first and third characters = (count("(")+1)*(count(")][]")+1). This is (0+1)*(1+1) = 2.
• Retaining the first and fifth characters = (count("(])")+1)*(count("[]")+1). This is (1+1)*(1+1) = 4.
• Retaining the first and last characters = (count("(])][")+1)*(count("")+1) This is (1+1)*(0+1) = 2.
As you can see, the sum is 11.

Obviously, you'll have to memoize the recursion to make sure you don't have exponential blowup.

My Solution.

 ```/* Topcoder SRM 686, D1, 250-pointer: BracketSequenceDiv1 * James S. Plank * Tue Oct 11 00:57:32 EDT 2016 */ #include #include #include #include #include #include #include #include #include #include using namespace std; class BracketSequenceDiv1 { public: map Cache; long long count(string s); }; long long BracketSequenceDiv1::count(string s) { int i; long long one; long long b, e; map ::iterator mit; /* Base case -- empty string equals 0 */ if (s.size() == 0) return 0; /* Memoization looks at the cache first. */ if (Cache.find(s) != Cache.end()) return Cache[s]; /* Set one to be the answer when you erase the first character. If the first character is a closing brace, that's all you can do, so return the answer in that case. */ one = count(s.substr(1)); if (s[0] == ')' || s[0] == ']') { Cache[s] = one; return one; } /* Otherwise, for each closing brace/parenthesis that matches the first character, split the string in two at that point, and recurse on the first half and the second half, adding one to account for empty strings. Add in the products. */ for (i = 1; i < s.size(); i++) { if ((s[0] == '(' && s[i] == ')') || (s[0] == '[' && s[i] == ']')) { b = count(s.substr(1, i-1))+1; e = count(s.substr(i+1))+1; one += (b*e); } } /* At the end, put the value into the cache, and return. */ Cache[s] = one; return one; } ```