Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

mochow's blog

By mochow, 4 years ago, In English,

Let us have a look at this series:

nm + (n-1)(m-1) + (n-2)(m-2) + (n-3)(m-3) + ...... + (until either n==1 or m==1).

Example:

Let, n=5, m=3. So we need to find the summation of

5.3 + 4.2 + 3.1

Well, what I need is a closed form. And how should I find out a closed form of such kind of series?

Thanks in advance! :)

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
4 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

let's assume that n < m
we know that 1*1 + 2*2 + 3*3 + ... + k*k = (2k + 1)(k + 1)k / 6
so we just need to calculate (m — n)*n + (m — n) * (n-1) + ... which is equal to (m — n) * (n + 1)n/2
so it will be (2n+1)(n+1)n/6 + (m-n)(n+1)n/2 = ((n+1)(n)(3m — n + 1))/6

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Okay I got it. Tricky and beautiful.

    PS: Did you participate Codechef's Kodeathon? You are so fast! :)

»
4 years ago, # |
Rev. 14   Vote: I like it +3 Vote: I do not like it

Let's suppose that n ≤ m.

S = n2·m - (n + m)n(n - 1) / 2 + (n - 1)n(2n - 1) / 6