10844 - Bloques

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

Moderator: Board moderators

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

10844 - Bloques

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

Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

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

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

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

Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

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

Gigi's Baby
New poster
Posts: 19
Joined: Thu May 02, 2002 5:47 am
Location: Zhongshan (Sun Yat-sen) University

Post by Gigi's Baby »

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

dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

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

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

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

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho »

little joey wrote:... In my implementation I only use addition ...
Hi, joey, can you reveal a little bit how's that possible?

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

Post by Larry »

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

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

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

Gigi's Baby
New poster
Posts: 19
Joined: Thu May 02, 2002 5:47 am
Location: Zhongshan (Sun Yat-sen) University

Post by Gigi's Baby »

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

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

Post by Larry »

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

dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan »

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

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post 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! ;)

pradeepr
New poster
Posts: 21
Joined: Fri May 25, 2007 11:52 am
Location: India

TLE!!

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

Post Reply

Return to “Volume 108 (10800-10899)”