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 .. » Sat Nov 22, 2003 6:24 pm

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] » Thu Feb 05, 2004 6:13 pm

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 » Mon Jul 12, 2004 1:12 pm

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 » Mon Jul 12, 2004 6:06 pm

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 » Thu Jul 15, 2004 9:32 am

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

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

Post by Sedefcho » Tue Feb 15, 2005 7:14 pm

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

User avatar
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 » Tue Feb 15, 2005 8:00 pm

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 » Tue Feb 15, 2005 9:06 pm

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

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

BigInteger

Post by Sedefcho » Wed Feb 16, 2005 1:09 am

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 » Wed Feb 16, 2005 3:15 am

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

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

10007

Post by Donotalo » Fri Sep 15, 2006 12:36 pm

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

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

Post by little joey » Fri Sep 15, 2006 1:39 pm

That is not the correct formula. Try again.

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

Post by Donotalo » Fri Sep 15, 2006 2:54 pm

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

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

Post by little joey » Fri Sep 15, 2006 3:25 pm

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 » Fri Nov 03, 2006 1:28 am

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