NWAYS - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

DIFFICULTY:

EASY

PREREQUISITES:

Hockey Stick Identity

PROBLEM:

Find the number of ways to move from all points in set X = \{(0,i): 1 \leq i \leq n \} to all point in set Y = \{(k,i): 1 \leq i \leq n \} using minimum number of steps.

EXPLANATION:

We are given two sets of points X and Y (described above) in 2-D grid, and we have to find the number of ways to move from all points in X to all points in Y using minimum number of steps. Note that only vertical and horizontal travelling is allowed and since we have to move from one point to another in minimum number of steps, we cannot visit a point twice.

The number of shortest paths from (0,0) to (m,n) in 2D grid is m+n \choose n. Using this result, in this problem, we essentially have to find the following term in which the first summation loops over the points in set X and second summation loops over the points in set Y.

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

Now the absolute value of j-i is a bug and we have to some how get rid of that absolute sign. The easiest way to do so is to consider the case when j \geq i and j < i . So, for any point i in set X, divide the points in set Y into 3 parts - lower y-points , upper y-points and y-point which is at the same level. Note that the upper and lower point cases are symmetrical. Hence, S can be written as follows

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

Now the only thing which is left, is to calculate \sum_{i=1}^n \sum_{j=i}^n {j-i+k \choose k}.

\begin{aligned} \sum_{i=1}^n \sum_{j=i}^n {j-i+k \choose k} &= \sum_{i=1}^n \sum_{j=k}^{n-i+k} \binom{j}{k} \\ &= \sum_{i=1}^n \binom{n-i+k+1}{k+1} \qquad \text{ Hockey Stick Identity } \\ &= \sum_{i=k+1}^{n+k} \binom{i}{k+1} \\ &= \binom{n+k+1}{k+2} \qquad \qquad \quad \ \text{ Hockey Stick Identity } \end{aligned}

The binomial terms can be calculated in \mathcal{O}(1) time if we have precomputed the factorial and inverse factorial. Hence, answer for every test case can be computed in \mathcal{O}(1) time.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter
Tester
Editorialist

4 Likes
2

links to solutions are not working!

3

could someone tell me where im going wrong.
I used dynamic programming using paths[i][j] where i=(difference in x coordinates) j=(diff in y) and paths is the number of paths with (diff in x=i) and (diff in y=j)
http://www.codechef.com/viewsolution/7056920

2 Likes
4

@siehpe your code gives WA for case 1000 1000 as while calculating the matrix you are not taking modulus which may cause overflow and especially the sum calculation part, take modulo there also and it will be fine

1 Like
5

@apptica thanks that worked!

1 Like
6

What is wrong with my solution @saurabh060792 ? http://www.codechef.com/viewsolution/7055277

1 Like
7

If I had wrote it in the form of double summation… Life would have been easier

1 Like
8

how is this no (2000006) achieved in many solutions to solve ?
j-i can be @ max 10^6-1 and k can be max 10^6 so that makes 2*10^6-1 ?

Thanks

1 Like
9

generally people just approximate the max usage of memory. I think this must be the reason.I used 2000005

10

This question may be good for other contests like Long Challenge or Cook-offs but they certainly aren’t supposed to be given for Lunchtimes . I have explained this in this post.

3 Likes
11

hi,
please check my code
what wrong with this??
http://www.codechef.com/viewsolution/7065805

1 Like
12

@deepak100 here is AC of your code http://www.codechef.com/viewsolution/7070722. Your statement sum = (2*sum%m - n)%m; has problem because modular operations of (a%m-b)%m is not valid always as a%m < b also basically what you have to do is add m to it and calculate modulo

1 Like
13

what is the formula to get 2nd last line from 3rd last line in your explaination??
∑i=1n(n−i+k+1k+1) Hockey Stick Identity
=∑i=k+1n+k(ik+1)

1 Like
14

thank u @apptica
i was confused with expression
sum=(2sum%m - n+m)%m; and sum=(2sum%m - n)%m; because if we add any no. m to a no. n and take mod with m then it must resultant 0 …ie. (n+m)%m==n

1 Like
15

I think he has used the identity C(n+r,r) for range of r . I read this from https://proofwiki.org/wiki/Sum_of_r%2Bk_Choose_k_up_to_n

16

Exactly. !

17

is there a need to evaluate inverse factorial

can’t we evaluate nCr(n, r) as (fact[n]/(fact[r]*fact[n-r])) % mod ???

18

@mohitbindal644 you cant do this because to store factorial of large numbers without mod will overflow the size of the defined variable whether it is even long double. Now in fact[] array you will store fact[i] as mod so you need to use inverse modulo

19

Please see it in reference to the theorem: http://www.artofproblemsolving.com/wiki/index.php/Combinatorial_identity#Hockey-Stick_Identity

20

I do not get how did you changed the mod to that formula with -n at the end… Can someone stepwise and split and derive please?