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][0] = 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[0][pos[0]][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][0] = 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[0][pos[0]][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;

            }

            return total;
        }
    }

    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);


    }
}