11250 - Working with Small Numbers

ardiankp · Post by **ardiankp** » Mon Jul 30, 2007 12:03 pm

Hi,

I've read that there's a closed formula for this problem.. and it shouldn't be too hard since there're many people solved it during the contest..

So.. any hint about the formula? I've thought about this problem for few days but no results..

For me, it seems that this problem is more difficult than calculating n-th harmonic number and calculating n!, of which to the best of my knowledge, there's no closed formula...

Thanks.

mf · Post by mf » Mon Jul 30, 2007 12:10 pm

First, you can separate i and j: sum_{i=1..n} sum_{j=1..m} (f(i)*g(j)) = (sum_{i=1..n} f(i)) * (sum_{j=1..m} g(j))

Then try to rewrite 1/(k(k+1)(k+2)(k+3)) as a linear combination of 1/k, 1/(k+1), 1/(k+2), 1/(k+3), and you'll get telescoping sums.

sclo · Post by **sclo** » Mon Jul 30, 2007 12:18 pm

Well, the formula for 1/(k(k+1)) should've been standard knowledge and this problem is just an extension.
I think it has to be of the following forms:
A + 1/(B(n+1)(n+2)...(n+k)) where k+1 is the number of factors in the denominator of the summand.

The problem here is getting tle for no obvious reason. I had to make weird optimizations to get AC in more than 9.3 secs.

ardiankp · Post by **ardiankp** » Mon Jul 30, 2007 12:41 pm

OK, thx, I think I got it

The keyword is telescoping.. hehe.. my math is poor..

Darko · Post by **Darko** » Mon Jul 30, 2007 6:35 pm

sclo wrote: The problem here is getting tle for no obvious reason. I had to make weird optimizations to get AC in more than 9.3 secs.

I am not sure if it is your gcd/division implementation, or maybe the way you are multiplying it. My sum for [1,n] is something like A/(C1*(A+C2)), where A=f(n) and C1,C2 are constants (and A is "nice"). Before I multiply two sums, I reduce the fractions, maybe you don't?

little joey · Post by **little joey** » Wed Aug 01, 2007 4:28 pm

sclo wrote:The problem here is getting tle for no obvious reason. I had to make weird optimizations to get AC in more than 9.3 secs.

By choosing the proper order of calculations, you never have to multiply two bigints or divide one by an other. Instead you only need multiplication of a bigint by a regular int and division by a regular int. This can save lots of time. (This under the assumption that the base of your bigints is >1000000003).