10844  Bloques
Moderator: Board moderators
10844  Bloques
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...
This almost makes me give up debugging...
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.
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.

 New poster
 Posts: 19
 Joined: Thu May 02, 2002 5:47 am
 Location: Zhongshan (Sun Yatsen) University
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 wordsize (base), but if I used a wordsize 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.
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 wordsize (base), but if I used a wordsize 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.

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Use 1000000000 (one billion) as basesize 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.
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.

 New poster
 Posts: 19
 Joined: Thu May 02, 2002 5:47 am
 Location: Zhongshan (Sun Yatsen) University

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
I forgot about using the Stiring numbers, though it is not optimal for this problem..
Check out http://www.algorithmist.com !
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:
I save all huge number in base 2^32.
I got it!
This is my code:
Code: Select all
Spoiler cuted off
I got it!
TLE!!
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??
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??