Page 1 of 2

10844 - Bloques

Posted: Tue May 10, 2005 10:14 am
by Cho
Just want to point out that the input contains 900 although the problem states that "Each natural number is less than 900".
This almost makes me give up debugging...

Posted: Tue May 10, 2005 11:01 am
by Dreamer#1
Yes you are right but hopefully this will be corrected soon. This is also the reason I got WA in this problem at the contest. Looking forward to the rejudgement. :)

Posted: Tue May 10, 2005 12:07 pm
by Cho
Do you know if anyone passed the time limit of this problem during the contest? My solution is far slower than 2 seconds.

Posted: Tue May 10, 2005 12:37 pm
by Dreamer#1
I don't think so. Actually during the contest I was really surprised with the 2 sec timelimit because I couldnot think of a solution that would run so fast at OJ, so I mailed a clarification and then later all the solutions were rejudged with increased timelimit but again this time due to the "900" in the judge data my TLE solution became WA. Now hopefully with corrected judge data it would be AC. I don't think a decent solution (with the correct algo) would ever be anywhere near 2 secs. May be if you optimize a lot (with the BigInt calculations) then it might be achieveable. But I'm sure that isn't what we were supposed to do.

Actually the problem is fine, just a little problem with the time limit. May be due to the different CPU speeds between the PC where judge solution was run and the UVA OJ. :)

Posted: Tue May 10, 2005 4:06 pm
by Gigi's Baby
Is it the Bell Number ?
I always got TLE. How to optimize?

Posted: Tue May 10, 2005 4:43 pm
by dumb dan
Yes, it's the Bell number.

As far as I can tell this is all about optimizing your bigint class (unless I'm missing something). I still have TLE myself (get to about n=620 before I TLE).

Currently my bigint class is using 10000 as word-size (base), but if I used a word-size that was a power of 2 I could use shiftoperations to speed up my multiplication considerably (probably enough to calculate all numbers before I TLE). However, then I have do a base conversion to get the numbers in base 10. But I figure since that's only n conversions as opposed to n^2 multiplications I need to do, it should be worth the trouble... I think.

Anyway, that's the best I can think of. If anyone has any tips for optimizing the bigint class, they are more than welcome.

Posted: Tue May 10, 2005 5:12 pm
by little joey
Use 1000000000 (one billion) as base-size for your bigint class. In my implementation I only use addition, so the maximum value for one 'digit' is 1999999999, from which the carry can be removed.
I agree with the ppl above that the time limit of 2 seconds was too tight for this problem. I guess it is just possible if you realy squeeze out the last cycle, but that can never be the object in a programming contest.

Posted: Tue May 10, 2005 6:05 pm
by Cho
little joey wrote:... In my implementation I only use addition ...
Hi, joey, can you reveal a little bit how's that possible?

Posted: Tue May 10, 2005 6:11 pm
by Larry
Use Bell's triangle... What's the more difficult way?

Posted: Tue May 10, 2005 6:50 pm
by Cho
oh.. got it now. Thank you very much. :D
Don't know about that before...
(I used the sum of Stirling number of second kind to get the Bell number.)

Posted: Tue May 10, 2005 7:36 pm
by Gigi's Baby
Thanks ! :)
I used Bell's triangle and got AC.

Posted: Tue May 10, 2005 7:42 pm
by Larry
I forgot about using the Stiring numbers, though it is not optimal for this problem..

Posted: Wed May 11, 2005 3:50 am
by dumb dan
Ah, yes... using Bell's triangle you only need addition. Thanks!

Posted: Mon Mar 06, 2006 4:04 pm
by Moha
I use Bell Triangle and my efficent add function but I got WA. I don't know why? at first I compute all bell numbers < 901 is it correct?
This is my code:

Code: Select all

Spoiler cuted off
I save all huge number in base 2^32.

I got it! ;)

TLE!!

Posted: Fri Jun 15, 2007 12:27 pm
by pradeepr
I used bell triangle to solve the problem and since it involves very large numbers I used strings and wrote a function for string addition .
and I was precalculating the results for the first 900 numbers.
I am sure that this precalculation is taking me more than 2 sec...
so wht s the better way to do this??