## 11444 - Sum

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

Moderator: Board moderators

### 11444 - Sum

We are summing basically

seq[i] * 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!
zuluaga
New poster

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

Obviously, by computing partial sums.

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

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

How many arrays for each k?
2,3,4, or 5 ?
zuluaga
New poster

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

k<=20

emotional blind
A great helper

Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh

One array for each k, i.e. 21 arrays in total.
mf
Guru

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

I did the same thing. kept the partial sums of i^k S[i] 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 ?
pvncad
New poster

Posts: 27
Joined: Sun Feb 18, 2007 2:14 pm

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

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

### 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?
Khaled_912
New poster

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

### Re: 11444 - Sum

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

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

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

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

Return to Volume CXIV

### Who is online

Users browsing this forum: No registered users and 0 guests