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.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Grid Walking
  5. Discussions

Grid Walking

Sort by

recency

|

50 Discussions

|

  • Tusenka
     + 0 comments

    What is wrong with the solution?

    #!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'gridWalking' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. INTEGER m
#  2. INTEGER_ARRAY x
#  3. INTEGER_ARRAY D
#
M=10**9+7
_dp_d=dict()
_dp_result=dict()
_dp_binomial_mod_M=[]

def _hash(m, x, d):
    return str(m)+" "+str(x)+" "+str(d)
    
def _dp_dimension(m, x, d):
    global _dp_d
    h=_hash(m, x, d)
    if h in _dp_d:
        return _dp_d[h]
    if m==1:
        _dp_d[h]=2 if x<d and x>1 else 1 if x<d or x>1 else 0
        return _dp_d[h]
    _dp_d[h]=0
    if x>1:
        _dp_d[h]+=_dp_dimension(m-1, x-1, d) % M
    if x<d:
        _dp_d[h]+=_dp_dimension(m-1, x+1, d) % M
    return _dp_d[h] % M
        
        
def _build_binomial_mod_M():
    global _dp_binomial_mod_M
    _dp_binomial_mod_M=[[1 for _ in range(102)] for _ in range(102)]
    _dp_binomial_mod_M[100][99]=100
    # TBD build binomial mod M only if bnomial mod is needed
    for i in range(101):
        _dp_binomial_mod_M[i][1]=i
    for i in range(2, 101):
        for j in range(2, i):
            _dp_binomial_mod_M[i][j]*= _dp_binomial_mod_M[i-1][j] % M + _dp_binomial_mod_M[i-1][j-1] % M %M
       
    
def _fact(n):
    global _dp_fact_mod_M
    return _dp_fact_mod_M[n]
    

def _binomial(x, k):
    global _dp_binomial_mod_M
    return _dp_binomial_mod_M[x][k]
    
    
def _next_walk(m, x, D):
    _count=0
    global _dp_d
    h=_hash(m, x, D)
    _build_binomial_mod_M()
    if h in _dp_d:
       return _dp_d[h]
    _last=0
    print( 20*"*", m, x, D)
    for i, d in enumerate(D):
        print(10*"*", d, 10*"*")
        _count=0
        if i==0:
           _last+=_dp_dimension(m, x[i], d)
           print(_last)
           continue
        for s in range(m):
            _count+=_last*_binomial(m, s)*_dp_dimension(m-s, x[i], d) % M % M
            print(f"binomial {_binomial(m, s)} _count {_count} m-s {m-s} dimension {_dp_dimension(m-s, x[i], d)}")
        _last+=_count
            
        print(f"m {m}, x[i], {x[i]}, d, {d},_dp_dimension {_dp_dimension(m, x[i], d)}")
    return _last % M    
    
    
def gridWalking(m, x, D):
    return _next_walk(m, x, D)
    # Write your code here

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input().strip())
    _build_binomial_mod_M()
    for t_itr in range(t):
        first_multiple_input = input().rstrip().split()

        n = int(first_multiple_input[0])

        m = int(first_multiple_input[1])

        x = list(map(int, input().rstrip().split()))

        D = list(map(int, input().rstrip().split()))

        result = gridWalking(m, x, D)

        fptr.write(str(result) + '\n')

    fptr.close()

  • Tusenka
     + 0 comments

    What is wrong with the solution?

    #!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'gridWalking' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. INTEGER m
#  2. INTEGER_ARRAY x
#  3. INTEGER_ARRAY D
#
M=10**9+7
_dp_d=dict()
_dp_result=dict()
_dp_binomial_mod_M=[]

def _hash(m, x, d):
    return str(m)+" "+str(x)+" "+str(d)
    
def _dp_dimension(m, x, d):
    global _dp_d
    h=_hash(m, x, d)
    if h in _dp_d:
        return _dp_d[h]
    if m==1:
        _dp_d[h]=2 if x<d and x>1 else 1 if x<d or x>1 else 0
        return _dp_d[h]
    _dp_d[h]=0
    if x>1:
        _dp_d[h]+=_dp_dimension(m-1, x-1, d) % M
    if x<d:
        _dp_d[h]+=_dp_dimension(m-1, x+1, d) % M
    return _dp_d[h] % M
        
        
def _build_binomial_mod_M():
    global _dp_binomial_mod_M
    _dp_binomial_mod_M=[[1 for _ in range(102)] for _ in range(102)]
    _dp_binomial_mod_M[100][99]=100
    # TBD build binomial mod M only if bnomial mod is needed
    for i in range(101):
        _dp_binomial_mod_M[i][1]=i
    for i in range(2, 101):
        for j in range(2, i):
            _dp_binomial_mod_M[i][j]*= _dp_binomial_mod_M[i-1][j] % M + _dp_binomial_mod_M[i-1][j-1] % M %M
       
    
def _fact(n):
    global _dp_fact_mod_M
    return _dp_fact_mod_M[n]
    

def _binomial(x, k):
    global _dp_binomial_mod_M
    return _dp_binomial_mod_M[x][k]
    
    
def _next_walk(m, x, D):
    _count=0
    global _dp_d
    h=_hash(m, x, D)
    _build_binomial_mod_M()
    if h in _dp_d:
       return _dp_d[h]
    _last=0
    print( 20*"*", m, x, D)
    for i, d in enumerate(D):
        print(10*"*", d, 10*"*")
        _count=0
        if i==0:
           _last+=_dp_dimension(m, x[i], d)
           print(_last)
           continue
        for s in range(m):
            _count+=_last*_binomial(m, s)*_dp_dimension(m-s, x[i], d) % M % M
            print(f"binomial {_binomial(m, s)} _count {_count} m-s {m-s} dimension {_dp_dimension(m-s, x[i], d)}")
        _last+=_count
            
        print(f"m {m}, x[i], {x[i]}, d, {d},_dp_dimension {_dp_dimension(m, x[i], d)}")
    return _last % M    
    
    
def gridWalking(m, x, D):
    return _next_walk(m, x, D)
    # Write your code here

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input().strip())
    _build_binomial_mod_M()
    for t_itr in range(t):
        first_multiple_input = input().rstrip().split()

        n = int(first_multiple_input[0])

        m = int(first_multiple_input[1])

        x = list(map(int, input().rstrip().split()))

        D = list(map(int, input().rstrip().split()))

        result = gridWalking(m, x, D)

        fptr.write(str(result) + '\n')

    fptr.close()

  • dehaka
     + 3 comments

    O(300^2 + n * m^2)

    long mod = 1000000007;

void combinatorial(vector<vector<long>>& binomial) {
    binomial[1][0] = 1;
    binomial[1][1] = 1;
    for (int n = 2; n <= 300; n++) {
        binomial[n][0] = 1;
        for (int k = 1; k <= n; k++) binomial[n][k] = (binomial[n-1][k-1] + binomial[n-1][k]) % mod;
    }
}

int gridWalking(int n, int m, const vector<int>& x, const vector<int>& D, const vector<vector<long>>& binomial) {
    vector<vector<long>> oneDimension(n+1, vector<long>(m+1)), multiDimension(n+1, vector<long>(m+1)), endPoint = {{0}};
    for (int i = 1; i <= n; i++) {
        oneDimension[i][0] = 1;
        endPoint.emplace_back(vector<long>(D[i-1] + 2));
        endPoint.back()[x[i-1]] = 1;
        for (int K = 1; K <= m; K++) {
            long total = 0, temp1 = 0, temp2;
            for (int point = 1; point <= D[i-1]; point++) {
                temp2 = endPoint[i][point];
                endPoint[i][point] = (temp1 + endPoint[i][point + 1]) % mod;
                total = (total + endPoint[i][point]) % mod;
                temp1 = temp2;
            }
            oneDimension[i][K] = total;
        }
    }
    multiDimension[1] = oneDimension[1];
    for (int i = 2; i <= n; i++) {
        multiDimension[i][0] = 1;
        for (int K = 1; K <= m; K++) {
            long temp = 0;
            for (int l = 0; l <= K; l++) temp = (temp + multiDimension[i-1][l] * (oneDimension[i][K-l] * binomial[K][l] % mod)) % mod;
            multiDimension[i][K] = temp;
        }
    }
    return multiDimension[n][m];
}

int main()
{
    int t, n, m, k;
    vector<vector<long>> binomial(301, vector<long>(301));
    combinatorial(binomial);
    cin >> t;
    for (int i = 1; i <= t; i++) {
        vector<int> x, D;
        cin >> n >> m;
        for (int j = 1; j <= n; j++) {
            cin >> k;
            x.push_back(k);
        }
        for (int j = 1; j <= n; j++) {
            cin >> k;
            D.push_back(k);
        }
        cout << gridWalking(n, m, x, D, binomial) << '\n';
    }
}

    • Tusenka
       + 1 comment

      why binomial[n][k] = (binomial[n-1][k-1] + binomial[n-1][k]) % mod;?

      • dehaka
         + 0 comments

        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)

    • Tusenka
       + 0 comments

      why x[i-1] not x[i]?

    • Tusenka
       + 0 comments

      very beatiful solution

  • walkeazeshoesan1
     + 0 comments

    Walkeaze provides a wide range of Clutches online in Pakistan. Discover the stylish clutch for women online at Walkeaze. Order your favorite clutch bag for ladies online at reasonable prices.

  • yashparihar729
     + 0 comments

    here is my solution in java, javascript, python, C, C++, Csharp HackerRank Grid Walking Problem Solution

Join us

Create a HackerRank account

Be part of a 26 million-strong community of developers

Already have an account?Log in