10157 - Expressions

[konsept]

I can't figure out why my solution is wrong for this problem.
here is my code:

[cpp]
#include <stdio.h>

long long ways[400][200];
long long sum[400][200];

long long getways( int n, int d );

long long anyN( int k, int f ){
long long m=0;
if ( k<0 || f<0 ) return 0;
if ( sum[k][f] != -1 ) return sum[k][f];
// for ( int i=0; i<=f; i++ ) m+=getways(k,i);

return (sum[k][f]=getways(k,f)+anyN(k,f-1));
}

long long getways( int n, int d ){
if ( !n ) return !d;
if ( n<0 ) return 0;
if ( d<0 ) return 0;
if ( n%2 ) return 0;

if ( ways[n][d]!=-1 ) return ways[n][d];

long long m=0;

int i;
for ( i=2; i<n; i++ ){
m+=2*getways(i-2,d-1)*anyN( n-i,d-1 );
m+=getways(i-2,d-1)*getways(n-i,d);
}
m+=getways(n-2,d-1);

//printf( "subProb(%d,%d)=%lld\n", n,d,m );
return ways[n][d]=m;
}

int main( void ){
FILE *in=stdin;
int i,j,k,n,d;

while ( fscanf( in, "%d %d", &n, &d )==2 ){
for ( i=0; i<400; i++ ) for ( j=0; j<200; j++ ) sum[j]=ways[j]=-1;
printf( "%lld\n", getways( n,d ) );
}

return 0;
}
[/cpp]

[tenshi]

"long long" is not enough, you need to calc in big numbers

[Adil]

hello.

what should be the output for these inputs:

100 2
100 19

thank you.

[cytse]

Here is my output

562949953421311
10441348575948087788919740

[LittleJohn]

I have a recurrence to solve this problem, but unluckily it's not efficient enough.
For each element t[n][d], it takes around 2*n*d*(bigInt ADD+bigInt MUL) computation time.
Although I implemented it by memoization, but the worst case can not avoid a large number of calculation.
I have no further idea about how to improve my program, so I want to ask if simpler recurrence exists?
Thanks!

[DemonCris]

I have a recurrence for this problem, but it is inefficent, too.
Here is my recurrence.

Code: Select all

             d-1            n-1
    c[n][d] = Σ  c[n-k][d] + Σ ( c[k-1][d-1] * s[n-k][d]) + c[n-1][d-1]
             k=1            k=d
                                                                                
    s[n][d] = c[n][d] + s[n][d-1]

, where n is the number of fully-paired parenthesis. The basic idea is as follows:
1. if k <= d-1
we can remove the prefix parenthesis. for example:
if we want to calculate c[5][3], we can calculate

() c[4][3] k=1
(()) c[3][3] k=2

2. if k >= d
In this case, the front side is hold for the depth d, therefore, the remaining
side is arbitrary depth.
ex: we want to calculate c[5][3]
((())) s[2][3] k=3

(()(())) s[1][3] k=4
((())())

and one special case
(c[4][2])


but for this recurrence, if the input is

Code: Select all

100 2 
100 19

my output is

Code: Select all

562949953421311
2966206932502021813736719

the first one of my output is the same as cytse's answer, but the
second one is not.

I don't know why, and the recurrence seems nice. (in fact, if the answer
is true, the time for worst case is still too long.)

Can someone help me indicate my fault?

[Adrian Kuegel]

Don't try to precalculate all values with DP. I optimized my DP precalculation, but the best I reached was 5 minutes runtime on my computer.
To solve this problem answer each query with another DP recurrence (it is not very difficult, but if you need help, you can write me a PM).

[Larry]

You mean memorization?

[little joey]

Just got accepted in 29.932 seconds, 0.068 seconds from TLE...

I don't precalculate all the answers, but memoize previously calculated results to speed it up. I also have some very efficient bignum functions (I know that from other problems), so I guess I use the wrong DP-method.

Each call to t_bignum expressions(int n, int d) makes 2*n*d recursive calls of expressions() with slightly lower values of n and d, and does n*d bignum multiplications and additions.

Im very interested in sub 0.1 second solutions. That is real solutions, not a 150*150 table of bignums compressed into a 32kb program.

[Adrian Kuegel]

My DP is O(n * d) for each query. And I need no multiplication, so each biginteger routine can be done in O(number of digits).
I don't want to give too much away here, but if you are interested, I can send you a pm with a description of my method.

[little joey]

O(n * d) and no multiplication... very interesting. I'll have to think it over seriously. Maybe I come back to you in a couple of days, but I want to think about it myself first. Thanks for your reply, Adrian.

[Yu Fan]

I think it could be solved with DP but I can't construct the recursive function, could some one help me?
Or.... it's not a DP problem?

[mf]

My solution is based on this function:

Let f(n,d) be the number of bracketings of length n, and depth at most d.
The function satisfies:

Code: Select all

f(n,d) = 0, if n < 0 or d < 0
f(n,d) = 1, if n = 0 and d >= 0
             ___
             \
f(n,d) =     /     f(k - 2, d - 1) f(n - k, d)
             ---
         2 <= k <= n
          k is even

And the answer to the original problem is given by f(n, d) - f(n, d - 1).

[Yu Fan]

Thanks, but could you explain how did you obtain this formula?I couldn't understand......


could you tell me the detail?

[mf]

Basically, every non-empty bracketing B of length n and depth <= d must be of this form:

B = (X)Y
where X, Y are some valid bracketings, possibly empty.

Let k be the length of the part `(X)'. Then the length of `X' is (k - 2) and the length of `Y' is (n - k).
Clearly, k must satisfy: 2 <= k <= n (otherwise the length of `X' or `Y' would become negative, which is impossible),
and k must also be an even integer (since every valid bracketing has even length.)

Since `B' has depth <= d, then, by the definition of depth, the depths of both `(X)' and `Y' are also <= d,
and the depth of `X' is <= (d - 1).

In summary, I've found that for fixed k:
1. `X' has length (k - 2), and depth <= (d - 1),
2. `Y' has length (n - k), and depth <= d.

Thus you have f(k-2, d-1) possible choices for `X' and f(n-k, d) choices for `Y'.
Applying the product rule of counting, you have: f(k-2, d-1) * f(n-k, d) choices for `B' (for fixed k.)

The total number of bracketings B is the sum of the above expression
over all possible values of k. (that's due to the sum rule of counting.)

That's why the recurrence works.

The function f(n,d) gives the number bracketings of depths 0, 1, ..., d.
To find the number of bracketings of only depth d, you need to compute f(n,d) - f(n,d-1).