We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
lol i dont remember how i did this question. this is wat i wrote as explanation, it explains the whole thing, i cant be bothered to read it to explain ur specific question
//A random walk in n dimensions can be split into random walk in each of the dimensions and analysed separately
//First, for each dimension i and 1 <= K <= m, oneDimension[i][K] calculates the number of random walks of length K
//within the interval [1, D[i]]:
//(1) For 1 <= point <= D[i], endPoint[i][K][point] stores the the number of length K random walks within [1, D[i]] that
// ends at point
//(2) endPoint[i][K+1][point] = endPoint[i][K][point-1] + endPoint[i][K][point+1]
//(3) oneDimension[i][K] = sum of all the endPoint[i][K][point] for every 1 <= point <= D[i]
//For n dimensions, let multiDimension[n][K] be the number of random walks within the corresponding n-dimensional cube defined by
//the D[i]'s
//The dynamic programming part is: any such walk can be split into a walk A in dimension n, and a walk B in the remaining n-1 dimensions.
//Let binomial[n][k] be the binomial coefficient
//Given a walk A of length l in dimension n, and a walk B of length K-l in the remaining n-1 dimensions,
//they can be combined to become a walk H of length K in n dimensions.
//There's binomial[K][l] many ways to insert the walk A into H, hence the number of length K walk in n dimensions that
//can be decomposed into a length l walk in dimension n, and a length K-l walk in the remaining n-1 dimensions, is:
// oneDimension[n][l] * multiDimension[n-1][K-l] * binomial[K][l]
//=> multiDimension[n+1][K] = sum of all the oneDimension[n][l] * multiDimension[n-1][K-l] * binomial[K][l] for every 0 <= l <= K
//The time of this algorithm is O(300^2 + n * m^2)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Join us
Create a HackerRank account
Be part of a 26 million-strong community of developers
Please signup or login in order to view this challenge
Grid Walking
You are viewing a single comment's thread. Return to all comments →
why binomial[n][k] = (binomial[n-1][k-1] + binomial[n-1][k]) % mod;?
lol i dont remember how i did this question. this is wat i wrote as explanation, it explains the whole thing, i cant be bothered to read it to explain ur specific question
//A random walk in n dimensions can be split into random walk in each of the dimensions and analysed separately
//First, for each dimension i and 1 <= K <= m, oneDimension[i][K] calculates the number of random walks of length K //within the interval [1, D[i]]: //(1) For 1 <= point <= D[i], endPoint[i][K][point] stores the the number of length K random walks within [1, D[i]] that // ends at point //(2) endPoint[i][K+1][point] = endPoint[i][K][point-1] + endPoint[i][K][point+1] //(3) oneDimension[i][K] = sum of all the endPoint[i][K][point] for every 1 <= point <= D[i]
//For n dimensions, let multiDimension[n][K] be the number of random walks within the corresponding n-dimensional cube defined by //the D[i]'s //The dynamic programming part is: any such walk can be split into a walk A in dimension n, and a walk B in the remaining n-1 dimensions.
//Let binomial[n][k] be the binomial coefficient //Given a walk A of length l in dimension n, and a walk B of length K-l in the remaining n-1 dimensions, //they can be combined to become a walk H of length K in n dimensions. //There's binomial[K][l] many ways to insert the walk A into H, hence the number of length K walk in n dimensions that //can be decomposed into a length l walk in dimension n, and a length K-l walk in the remaining n-1 dimensions, is: // oneDimension[n][l] * multiDimension[n-1][K-l] * binomial[K][l] //=> multiDimension[n+1][K] = sum of all the oneDimension[n][l] * multiDimension[n-1][K-l] * binomial[K][l] for every 0 <= l <= K
//The time of this algorithm is O(300^2 + n * m^2)