### PROBLEM LINK:

### DIFFICULTY:

EASY

### PREREQUISITES:

### 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**.

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

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

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.