You are not logged in. Please login at www.codechef.com to post your questions!

×

Small doubt in nways editorial

I am trying to solve NWAYS problem.I read the Editorial but I am not able to understand how they got the relation
$S = 2\sum_{i=1}^{n}\sum_{j=i}^{n} \binom{j-i+k}{k}-n $
It would be a great help if any one explain me with this.. :)

asked 27 Mar '16, 10:43

pallesai's gravatar image

4★pallesai
176830
accept rate: 17%

edited 27 Mar '16, 10:43


First consider the case when y-coordinate is less than x-coordinate. In that case |j-i| = i-j.

Next, Consider the case when y-coordinate is more than y-coordinate. In that case |j-i| = j-i.

Finally, consider the case when y-coordinate is equal to x-coordinate. In that case |j-i| = 0.

The first 2 cases are equivalent. Hence the factor of 2 comes. For the last case Combination part i.e. nCr (with n = k and r = k) gave 1, which summed upto n. Since 2 was multiplied, so they subtracted 'n' (Similar to n = 2n - n).

Hope it is clear.

link

answered 27 Mar '16, 21:29

likecs's gravatar image

6★likecs
3.7k2380
accept rate: 9%

Here is the expression you are talking about.

$S = \sum_{i=1}^n \sum_{j=1}^n {|j-i|+k \choose k}$

Now, from the definition of absolute value,

alt text

Now, as the mod function is symmetric, the expression can be modified as shown below.

$S = \sum_{i=1}^n \sum_{j=1}^n {|j-i|+k \choose k} \\= 2\sum_{i=1}^n \sum_{j=i+1}^n {j-i+k \choose k} + \sum_{i=1}^n {k \choose k} \\= 2\sum_{i=1}^n \sum_{j=i+1}^n {j-i+k \choose k} + n \\= 2\sum_{i=1}^n \sum_{j=i}^n {j-i+k \choose k} - n$

Hope this helps.

link

answered 30 Mar '16, 18:46

ash_code's gravatar image

3★ash_code
475114
accept rate: 15%

edited 30 Mar '16, 18:47

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×884

question asked: 27 Mar '16, 10:43

question was seen: 556 times

last updated: 30 Mar '16, 18:47