Let X be the set of correctly built parenthesis expressions. The elements of X are strings consisting only of the characters “(” and “)”, defined as follows:
- The empty string belongs to X.
- If A belongs to X, then (A) belongs to X.
- If both A and B belong to X, then the concatenation AB belongs to X.
For example, the strings ()(())() and (()(())) are correctly built parenthesis expressions, and therefore belong to the set X. The expressions (()))(() and ())(() are not correctly built parenthesis expressions and are thus not in X.
The length of a correctly built parenthesis expression E is the number of single parenthesis (characters) in E. The depth D(E) of E is defined as follows:
For example, ()(())() has length 8 and depth 2. Write a program which reads in n and d and computes the number of correctly built parenthesis expressions of length n and depth d.
Input
The input consists of pairs of integers n and d, with at most one pair per line and 2
n300, 1d150. The input may contain empty lines, which you don’t need to consider.
Output
For every pair of integers in the input, output a single integer on one line – the number of correctly built parenthesis expressions of length n and depth d.
Sample Input
6 2 300 150
Sample Output
3 1
Note: The three correctly built parenthesis expressions of length 6 and depth 2 are (())(), ()(()), and (()()).
Explanation:
So, generally speaking, the steps to this problem are find the recurrence, implement the recurrence, implement memoization for it and then use BigNums.
I found finding the recurrence to be rather difficult here, but eventually managed to find something right out of the depth of hell. Okay, ready for it?
F(l, d) = F(l-2, d) + summation (k = 2, k d), so basically Catalan number of k and subtract from it the number of correct expressions with depth more than d.
Here’s my rationale for this. Imagine how correct expressions of length l are formed if you are given correct expressions of length l-2. Let’s take the example of correct expressions of length 6. So intially we have the new parantheses to the left and the old parentheses to the right.
() (()), now while the new parentheses are to the left alone, we can run through all the correct expressions of length 4.
() () (), and that’s it basically, since there are 2 correct expresions of length 4. Now move one of the old parentheses inside the new ones.
( () ) () , and we would run through all the correct expressions of length 2 and multiply them by the correct expressions of length 2 again, since we have one set inside the new parentheses and one set outside. Finally, we move the last one inside and do the same thing.
( () () )
( ( ( ) ) ) and that’s it, we got 5 correct expressions of length 6.
Now, our problem involves correct ones of certain length and depth. So while running through the expressions at any point, we want only those ones that are compatible. Hence, we do something like this
() (()), how many times can the left one have depth k, how many times can right one have depth k, how many times when the left one has depth k, the right one has more depth than k, and how many times when the right one has depth k, the left one has more depth than k. And we repeat this for every step of the calculation.
This took 6 seconds to run on the PC judge, which is not so bad since the time limit is 10 seconds. I think any solution that doesn’t do offline computation of values will be around this mark.
P.S. I wrote this solution in Java again so I can make use of BigNum.
import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;
public class Main {
static BigDecimal CNs[] = new BigDecimal[151];
public static BigDecimal CN(int n)
{
if (CNs[n] != null) return CNs[n];
BigDecimal a = new BigDecimal("1");
BigDecimal b = new BigDecimal("1");
for (int i=n+1, j = 1; i<= 2*n; i++, j++) { a = a.multiply(BigDecimal.valueOf(i)); b = b.multiply(BigDecimal.valueOf(j)); } b = b.multiply(BigDecimal.valueOf(n + 1)); a = a.divide(b); CNs[n] = a; return a; } static BigDecimal dp[][]; public static BigDecimal calc(int l, int d) { if (dp[l][d] != null) return dp[l][d]; if (d*2 > l) return BigDecimal.valueOf(0);
if (d*2 == l) return BigDecimal.valueOf(1);
if (d == 1) return BigDecimal.valueOf(1);
BigDecimal a = calc(l-2, d);
BigDecimal c, f, e, nTooBig, c1, c2;
for (int i=2; i<=l-2; i+=2)
{
nTooBig = BigDecimal.valueOf(0);
for (int j=d+1; calc(l-i-2,j).compareTo(BigDecimal.valueOf(0)) != 0; j++)nTooBig = nTooBig.add(calc(l-i-2,j));
c1 = CN( (l-i-2)/2).subtract(nTooBig);
c = calc(i, d-1).multiply(c1);
nTooBig = BigDecimal.valueOf(0);
for (int j=d; calc(i,j).compareTo(BigDecimal.valueOf(0)) != 0; j++)nTooBig = nTooBig.add(calc(i,j));
c2 = CN(i/2).subtract(nTooBig);
e = c2.subtract(calc(i, d-1));
f = calc(l-i-2, d).multiply(e);
a = a.add( f.add(c));
}
dp[l][d] = a;
return dp[l][d];
}
public static void main(String args[])
{
Scanner s = new Scanner(System.in);
dp = new BigDecimal[301][];
for (int i=0; i<301; i++)dp[i] = new BigDecimal[151];
int l, d;
while(s.hasNextInt())
{
l = s.nextInt();
d = s.nextInt();
System.out.printf("%s\n", calc(l,d).toString());
}
}
}
3)
b
n < 231).
where m and n are relatively prime. The idea is to start with two fractions 
,
and then repeat the following operation as many times as desired:
between two adjacent fractions 
and 
.
,
,
,
,
,
,
,
,
down to 
, then right to 
, then right to 
, then left to 
. We can consider LRRL to be a representation of 
Coding Strife 