### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# Gridwalking challenge

Sharing is caring!

Problem statement
You are situated in an $N$ dimensional grid at position $(x_1,x_2, \dots ,x_N)$. The dimensions of the grid are $(D_1,D_2, \dots ,D_N)$
In one step, you can walk one step ahead or behind in any one of the $N$ dimensions. (So there are always $2 \times N$ possible different moves).

In how many ways can you take $M$ steps such that you do not leave the grid at any point? You leave the grid if at any point $x_i$, either $x_i \le 0$
or $x_i \textgreater D_i$.

Input Format
The first line contains the number of test cases T. T test cases follow. For each test case, the first line contains N
and $M$, the second line contains the current position $pos = [ x_1,x_2, \dots ,x_N ]$ and the 3rd line contains $D_1,D_2, \dots ,D_N$.

Output Format
Output $T$ lines, one corresponding to each test case. Since the answer can be really huge, output it modulo $1000000007$.

Constraints
$1 \le T \le 10$
$1 \le N \le 10$
$1 \le M \le 300$
$1 \le D_i \le 100$
$1 \le x_i \le Di$

#### Solution

We will solve this using Dynamic Programming and with the help of combinatorics. So let us define some helper functions first.

Fast-pow function
In order to reduce computation time we define a function pow(long x, long n, long p) that raises x to the power of n modulo p ($x^n\mod p$). We will use a method called Exponentiation by squaring.

N choose K $\binom{n}{k}$
Next we will need an Binomial coefficient function c(long n, long k, long p) that also performs a modulo p operation.

#### Precomputations

Now that we have implemented our helper function, we can finally discuss some precomputations we will make before proceeding with the main algorithm.

Solve for 1 dimension
We will first solve the problem for one dimension. First define dp[i][k] = new long[n][m + 1] which holds the number of ways to take $k$ steps when currently at position $i$ where n is the length of the dimension.

When $k = 0$ there is only one way to take 0 steps from a give position $i$.

For $k \textgreater 0$ we have 3 different cases:
1. If $i=0$ (we are on the left edge): in that case we have 1 way to take 1 step to the right plus $k-1$ steps from position $i+1$.
2. If $i=n-1$ (we are on the right edge): in that case we have 1 way to take 1 step to the left plus $k-1$ steps from position $i-1$.
3. If current position $i$ is neither on the left nor on the right edge we can take a step to the left and then $k-1$ remaining steps from position $i-1$ or we can take one step to the right and then $k-1$ remaining steps from position $i+1$.

Generate dp array for all dimensions
Next we generate a dp array from the previous step for all dimensions and store it in dimensionsDP = new long[dimensions.length][][]

#### Main algorithm

Once we have our dimensionsDP[][][] array, we can proceed with the main algorithm. The principle is as follows:

• Take $M-k$ steps in dimension $i$. And $k$ steps in dimensions $\textless i$.
• The number of $M-k$ steps in dimension $i$ can be read from the 1-D matrix. Let that number be $x$.
• The number of $k$ steps in any dimension $\textless i$ can also be read from the 1-D matrix. Let that number be $y$.
• We have to find out in how many ways we can choose $k$ steps out of possible $M$. This is $\binom{M}{k}$.
• For example:
Let $M=3$ and $k=2$. Then we can choose which $k$ steps out of $M$ we want to take in a dimension $\textless i$. Those can be (Step1, Step2) or (Step1, Step3) or (Step2, Step3) = $\binom{M}{k} = \frac{3!}{k!(3-k)!} = \frac{3!}{2!} = 3$
• So in order to compute in how many ways we can take $M-k$ steps in $currentDimension$ and $k$ steps in a dimension $\textless currentDimension$ we do: dp[currentDimension][pos[currentDimension]][M - k] * c(M, k) * solve(k, currentDimension - 1)
First multiplicand is the number ways we can take $M-k$ steps in current dimension when we are at position pos[currentDimension]. For every such way we have c(M,k) ways to choose $k$ steps that we want to walk in another dimension, and for every of the c(M,k) ways we can walk solve(k, currentDimension - 1) paths. With solve(k, currentDimension - 1) we solve the problem for the remaining $k$ steps in dimensions $\textless currentDimension$.
• Repeat the above steps for $k \in [0,M]$.
• The ending condition for the recursive call of solve(k, dimension) is when dimension = 0 at which point we return dp[0][pos[0]][M].

Full code