10844 - Bloques

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

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

[Cho]

Do you know if anyone passed the time limit of this problem during the contest? My solution is far slower than 2 seconds.

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

[Gigi's Baby]

Is it the Bell Number ?
I always got TLE. How to optimize?

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

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

[Cho]

... In my implementation I only use addition ...

Hi, joey, can you reveal a little bit how's that possible?

[Larry]

Use Bell's triangle... What's the more difficult way?

[Cho]

oh.. got it now. Thank you very much.
Don't know about that before...
(I used the sum of Stirling number of second kind to get the Bell number.)

[Gigi's Baby]

Thanks !
I used Bell's triangle and got AC.

[Larry]

I forgot about using the Stiring numbers, though it is not optimal for this problem..

[dumb dan]

Ah, yes... using Bell's triangle you only need addition. Thanks!

[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!

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