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