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';
    }
}

  • 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