10007 - Count the Trees

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

Moderator: Board moderators

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

Oh thx~~ :D
I forget Catalan number completely~~ :oops:
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

alex[LSD]
Learning poster
Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA
Contact:

Post by alex[LSD] »

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...
The more contests are held, the happier I am.

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise »

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 !

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

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

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise »

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

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho »

Larry,

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

Well the right formula is

Code: Select all

( 2*N ) !   /  (N+1 ) !  
At least these are the values in the sample output of problem 10007
( if we assume that the input value is N ).

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

one more solution in java for 10007

Post by Sedefcho »

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.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

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

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

BigInteger

Post by Sedefcho »

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.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

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

Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am
Location: Bangladesh

10007

Post by Donotalo »

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?
Image

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

Post by little joey »

That is not the correct formula. Try again.

Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am
Location: Bangladesh

Post by Donotalo »

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 :)
Image

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

Post by little joey »

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

Scottathon
New poster
Posts: 9
Joined: Fri Nov 03, 2006 1:25 am
Location: Canada

Post by Scottathon »

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

Thanks.

Post Reply

Return to “Volume 100 (10000-10099)”