11444 - Sum

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

Moderator: Board moderators

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

11444 - Sum

Post by zuluaga » Mon Mar 31, 2008 3:17 am

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:

Post by mf » Mon Mar 31, 2008 3:45 am

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

Post by zuluaga » Mon Mar 31, 2008 4:47 am

How many arrays for each k?
2,3,4, or 5 :roll: ?

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Mon Mar 31, 2008 5:09 am

k<=20

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

Post by mf » Mon Mar 31, 2008 5:11 am

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

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

Post by pvncad » Mon Mar 31, 2008 7:15 am

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:

Post by mf » Mon Mar 31, 2008 8:59 am

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

Post by Khaled_912 » Mon Apr 21, 2008 9:26 pm

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

Post by mf » Mon Apr 21, 2008 9:30 pm

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.

Post Reply

Return to “Volume 114 (11400-11499)”