## [f]izzbuzzer

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

public static long pow(long x, long n, long p) {
long result = 1;
while (n > 0) {
if ((n & 1) == 1) {
result = (result * x) % p;
}

x = (x * x) % p;
n = n >> 1;
}

return result;
}


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.

public static long c(int n, int k, long p) {
// C(n,k) = n!/(k!*(n-k)!)

long numerator = 1;
for (int i = 0; i < k; i++) {
numerator = (numerator * (n - i)) % p;
}

long denominator = 1;
for (int i = 1; i <= k; i++) {
denominator = (denominator * i) % p;
}

return (numerator * (pow(denominator, p - 2, p))) % p;
}


#### 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 (int i = 0; i < n; i++) {
dp[i] = 1;
}


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$.

for (int k = 1; k <= m; k++) {
for (int i = 0; i < n; i++) {
if (i == 0) {
// We are on the left edge
dp[i][k] = dp[i + 1][k - 1];
} else if (i == n - 1) {
// We are on the right edge
dp[i][k] = dp[i - 1][k - 1];
} else {
dp[i][k] = (dp[i - 1][k - 1] + dp[i + 1][k - 1]) % MODULO;
}
}
}


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][][]

private static long[][][] generateDP(int[] dimensions, int m) {
long[][][] dimensionsDP = new long[dimensions.length][][];
for (int d = 0; d < dimensions.length; d++) {
int n = dimensions[d];
dimensionsDP[d] = solve1d(n, m);
}

return dimensionsDP;
}


#### 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[pos][M].

Full code

public class GridWalking {

private static final long MODULO = 1000000007;
private static long[][] cache;

private static long[][] solve1d(int n, int m) {
// dp[i][k] = number of ways to take k steps when currently at position i
long[][] dp = new long[n][m + 1];

// Init dp
for (int i = 0; i < n; i++) {
dp[i] = 1;
}

if (n == 1) {
return dp;
}

for (int k = 1; k <= m; k++) {
for (int i = 0; i < n; i++) {
if (i == 0) {
// We are on the left edge
dp[i][k] = dp[i + 1][k - 1];
} else if (i == n - 1) {
// We are on the right edge
dp[i][k] = dp[i - 1][k - 1];
} else {
dp[i][k] = (dp[i - 1][k - 1] + dp[i + 1][k - 1]) % MODULO;
}
}
}

return dp;
}

private static long[][][] generateDP(int[] dimensions, int m) {
long[][][] dimensionsDP = new long[dimensions.length][][];
for (int d = 0; d < dimensions.length; d++) {
int n = dimensions[d];
dimensionsDP[d] = solve1d(n, m);
}

return dimensionsDP;
}

private static long solve(int[] pos, int m, int currentDimension, long[][][] dp) {
if (currentDimension == 0) {
return dp[pos][m];
} else {
long total = 0;

for (int k = 0; k <= m; k++) {
long smallerDimensions = cache[currentDimension - 1][k];
if (smallerDimensions == 0) {
smallerDimensions = solve(pos, k, currentDimension - 1, dp) % MODULO;
cache[currentDimension - 1][k] = smallerDimensions;
}

long cnk = c(m, k, MODULO);
total = (total + ((dp[currentDimension][pos[currentDimension]][m - k] * ((smallerDimensions * cnk) % MODULO)) % MODULO)) % MODULO;

}

}
}

public static long pow(long x, long n, long p) {
long result = 1;
while (n > 0) {
if ((n & 1) == 1) {
result = (result * x) % p;
}

x = (x * x) % p;
n = n >> 1;
}

return result;
}

public static long c(int n, int k, long p) {
// C(n,k) = n!/(k!*(n-k)!)

long numerator = 1;
for (int i = 0; i < k; i++) {
numerator = (numerator * (n - i)) % p;
}

long denominator = 1;
for (int i = 1; i <= k; i++) {
denominator = (denominator * i) % p;
}

return (numerator * (pow(denominator, p - 2, p))) % p;
}

public static void main(String[] args) {
int m = 69; //In how many ways can you take M steps such that you do not leave the grid at any point?
int[] pos = {3, 6, 1, 19, 6};
for (int p = 0; p < pos.length; p++) {
pos[p] = pos[p] - 1;
}

int[] dimensions = {6, 13, 1, 27, 17};
long[][][] dp = generateDP(dimensions, m);
cache = new long[dimensions.length][m + 1];
long result = solve(pos, m, dimensions.length - 1, dp);
System.out.println(result);

}
}