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

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

10844 - Bloques

Post by Cho » Tue May 10, 2005 10:14 am

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

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

Post by Dreamer#1 » Tue May 10, 2005 11:01 am

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

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

Post by Cho » Tue May 10, 2005 12:07 pm

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

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

Post by Dreamer#1 » Tue May 10, 2005 12:37 pm

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

User avatar
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 » Tue May 10, 2005 4:06 pm

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

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

Post by dumb dan » Tue May 10, 2005 4:43 pm

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.

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

Post by little joey » Tue May 10, 2005 5:12 pm

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.

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

Post by Cho » Tue May 10, 2005 6:05 pm

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 » Tue May 10, 2005 6:11 pm

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

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

Post by Cho » Tue May 10, 2005 6:50 pm

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

User avatar
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 » Tue May 10, 2005 7:36 pm

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 » Tue May 10, 2005 7:42 pm

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

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

Post by dumb dan » Wed May 11, 2005 3:50 am

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 » Mon Mar 06, 2006 4:04 pm

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 » Fri Jun 15, 2007 12:27 pm

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