## [f]izzbuzzer

### Looking for good programming challenges?

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

# Gridwalking challenge

Problem statement
You are situated in an dimensional grid at position . The dimensions of the grid are In one step, you can walk one step ahead or behind in any one of the dimensions. (So there are always possible different moves).

In how many ways can you take steps such that you do not leave the grid at any point? You leave the grid if at any point , either or .

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 , the second line contains the current position and the 3rd line contains .

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

Constraints     #### 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 ( ). 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 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 steps when currently at position where n is the length of the dimension.

When there is only one way to take 0 steps from a give position .

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


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

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 steps in dimension . And steps in dimensions .
• The number of steps in dimension can be read from the 1-D matrix. Let that number be .
• The number of steps in any dimension can also be read from the 1-D matrix. Let that number be .
• We have to find out in how many ways we can choose steps out of possible . This is .
• For example:
Let and . Then we can choose which steps out of we want to take in a dimension . Those can be (Step1, Step2) or (Step1, Step3) or (Step2, Step3) = • So in order to compute in how many ways we can take steps in and steps in a dimension we do: dp[currentDimension][pos[currentDimension]][M - k] * c(M, k) * solve(k, currentDimension - 1)
First multiplicand is the number ways we can take steps in current dimension when we are at position pos[currentDimension]. For every such way we have c(M,k) ways to choose 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 steps in dimensions .
• Repeat the above steps for .
• 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);

}
}