10157 - Expressions

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

konsept
New poster
Posts: 22
Joined: Wed Dec 19, 2001 2:00 am
Location: Waterloo, Canada
Contact:

10157 - Expressions

Post by konsept » Wed Jul 17, 2002 10:26 pm

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
New poster
Posts: 14
Joined: Tue Jun 25, 2002 8:50 am

Post by tenshi » Tue Sep 17, 2002 1:05 pm

"long long" is not enough, you need to calc in big numbers
http://www.ioiforum.org/en/

A problem discussing forum.
Welcome to discuss problems in it!

Adil
Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:

Post by Adil » Thu Apr 24, 2003 9:15 am

hello.

what should be the output for these inputs:

100 2
100 19

thank you.

User avatar
cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:

Post by cytse » Sat Apr 26, 2003 2:47 pm

Here is my output
562949953421311
10441348575948087788919740

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Post by LittleJohn » Thu Jul 24, 2003 3:18 pm

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! :wink:

User avatar
DemonCris
New poster
Posts: 25
Joined: Sun Feb 24, 2002 2:00 am
Location: Taiwan

Post by DemonCris » Sat Jul 26, 2003 4:46 am

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Jul 27, 2003 1:26 pm

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Mon Jul 28, 2003 4:14 pm

You mean memorization?

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Apr 29, 2004 4:02 pm

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Thu Apr 29, 2004 5:13 pm

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Apr 29, 2004 6:15 pm

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.

User avatar
Yu Fan
New poster
Posts: 26
Joined: Thu Nov 13, 2003 3:52 am

10157

Post by Yu Fan » Tue Jun 21, 2005 8:16 am

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue Jun 21, 2005 12:33 pm

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).

User avatar
Yu Fan
New poster
Posts: 26
Joined: Thu Nov 13, 2003 3:52 am

Post by Yu Fan » Tue Jun 21, 2005 2:08 pm

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


could you tell me the detail? :roll:

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue Jun 21, 2005 6:48 pm

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).

Post Reply

Return to “Volume 101 (10100-10199)”