OJ Board

Oh thx~~
I forget Catalan number completely~~

Whoa!
I was a about to start coding that F(0)*F(N-1)+F(1)*F(N-2)+... solution. But when you see that F(N) = C(N,2N) - C(N+1,2N) = 2N!/(N+1)!N!
... you just dont want to do it.
Thanks, I will remember it now...

Hi

I tried to use the nice solution mentionned above (after having found it by myself). Nevertheless, still TLE
Is it that my BigInteger routines are *really* slow (that alas might be), or is there a hint to accelerate the calculation ?

Thank you !

Ya, you'll need to optimize your BigInt a little, since I did a very trivial implementation, and in Java, and it still AC'ed (though with a slow time..) It's either that or you may not be handling the IO correctly..

Thanks ! I'll try that
Btw, are Java's BigInteger class allowed in regional contests and/or in world finals ?

Larry,

Obvously the formula you have given is wrong,
I think you've made a typo.

Well the right formula is At least these are the values in the sample output of problem 10007
( if we assume that the input value is N ).

The standard Java class BigInteger is not allowed by
the Online Judge, I do not know if it is acceptable in
ACM or other programming contests.

By the way in Java I get ACC on this problem in
approximately 0.25 secs.

If someone needs some hints
( especially if this someone attacks that
problem in Java ), I will be happy to give him
some hints.

Java is allowed on most ACM competitions.. though that's actually up to each site..

Sure, Java is allowed.

I just said that the standard Java class
java.math.BigInteger
is not allowed by the Online Judge of this site.

Each site as in each regional contest site, I meant.

Java here is version 1.2, where BigInteger is implemented in 1.3 and later, hence the lack of support. It isn't that that the class that is specifically banned. (As far as I understand it..)

i'm having problem with generating catalan number efficiently. here is what i did:

Catalan(n+1) = (2 * (2n + 1) * Catalan(n)) / (n + 2)

it gives me some wrong catalan numbers since the numerator may not properly divisible by (n + 2). any solution to this problem?

That is not the correct formula. Try again.

that is actually valid equation. source: http://mathworld.wolfram.com/CatalanNumber.html

however, problem was in my code. i corrected it and first got TLE. then after some optimization, i got AC

Duh. Of course you're right. I was looking in the wrong place in my source code...

Can someone post some input and output?
My program passes the sample input, but I keep getting wrong answer.

Thanks.