## 11444 - Sum

Moderator: Board moderators

zuluaga
New poster
Posts: 5
Joined: Sat Jan 05, 2008 9:17 pm

### 11444 - Sum

We are summing basically

seq * i^k

but for different ranges [a,b]. How to reduce this to run
in time? I cannot see how to precompute for this. Thanks!

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Obviously, by computing partial sums.

For this problem, you just need to keep several arrays with partial sums, for each possible k.

zuluaga
New poster
Posts: 5
Joined: Sat Jan 05, 2008 9:17 pm
How many arrays for each k?
2,3,4, or 5 ?

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
k<=20

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
One array for each k, i.e. 21 arrays in total.

New poster
Posts: 27
Joined: Sun Feb 18, 2007 2:14 pm
I did the same thing. kept the partial sums of i^k S and
computed fF(k, a, b) using binomial expansion. Still I am getting WA?
it was running fine for sample inputs and all of my own testcases.

Could someone provide some inputs ?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
It shouldn't be hard for you to write a brute-force program, and check your answers with it on random big cases.

And look out for overflows.

Khaled_912
New poster
Posts: 33
Joined: Fri Jan 06, 2006 5:51 pm

### Re: 11444 - Sum

I understood how to deduce the answer from the partial sums when K = 1, but I failed to generalize it for K > 1.
How can the binomial expansion help me here?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 11444 - Sum

Use binomial formula to expand (i-a+1)^k in terms of powers of i.

For K=2:
sum(seq * (i + (1-a))^2) =
sum(seq*i^2 + 2(1-a)*seq*i + (1-a)^2*seq) = sum(seq*i^2) + 2(1-a)*sum(seq*i) + (1-a)^2 * sum(seq).

Sums like sum(seq*i^2), sum(seq*i), etc can be done with a precomputation.