Python, O(N*(N+R+C)) reduction to 1D [Very Fast]


  • 0

    Following @StefanPochmann 's excellent suggestion, let inside(t) be the number of paths that remain inside the board after t moves. Then the number of paths that exit the boundary on the t+1'th move is 4*inside(t) - inside(t+1).

    Suppose we are to make t moves. We'll make k horizontal moves and t-k vertical moves. We can shuffle the order of these moves in binom(t, k) ways (the binomial coefficient.) So in total:
    inside(t) = sum_{k=0..t} (number of ways to stay on the board in k moves horizontally) * (number of ways to stay on the board in t-k moves vertically) * binom(t, k).

    We can find in advance our answers to the 1D problem by a simple dp. There probably exists an even faster approach for this, but I can't think of one right now.

    def findPaths(self, R, C, N, sr, sc):
        MOD = 10**9 + 7
        
        def binom_all(n):
            ans = [1]
            r = 1
            for i in xrange(1, n+1):
                r *= n - i + 1
                r /= i
                ans.append(r)
            return ans
        
        def solve_1D(A):
            ans = [1]
            for time in xrange(N+1):
                Anew = [0] * len(A)
                inside = 0
                for i, u in enumerate(A):
                    if i >= 1:
                        Anew[i-1] += u
                        inside += u
                    if i < len(A) - 1:
                        Anew[i+1] += u
                        inside += u
                A = Anew
                ans.append(inside)
            return ans
        dprow = solve_1D([+(r == sr) for r in xrange(R)])
        dpcol = solve_1D([+(c == sc) for c in xrange(C)])
        binoms = [binom_all(n) for n in xrange(N+1)]
        
        def inside(t):
            ans = 0
            for k in xrange(t+1):
                ans += dprow[k] * dpcol[t-k] * binoms[t][k]
            return ans % MOD
        
        S = sum(inside(t) for t in xrange(N))
        return (3*S - inside(N) + inside(0))%MOD
    

  • 0
    A

    Excellent. That was a neat trick of using 4*inside(t) - inside(t+1).

    I used slightly different technique but the essence is the same. I instead also calculated number of ways to reach the boundary in a 1D array and used that to calculate the number of ways to exit the boundary.
    I like your trick better though. :)

    class Solution {
    public:
        using LL = long long;
        int findPaths(int m, int n, int N, int i, int j) {
          if (n==0 || m==0) return 0;
    
          int mod = 1000000007;
          
          // using dynamic programming to calculate combinations.
          LL C[52][52];
          C[0][0] = C[0][1] = 1;
          for (int a=1; a<=N; a++) {
            C[a][0] = C[a][a] = 1;
            for (int b=1; b<a; b++)
              C[a][b] = (C[a-1][b] + C[a-1][b-1]) % mod;
          }
          
          vector<LL> H(N+2,0), V(N+2, 0);  // H = Horizontal, V = Vertical
          vector<LL> HB(N+2,0), VB(N+2, 0);  // HB = Horizontal Boundary, VB = Vertical Boundary
          LL dp[2][52];
          int t = 0;
          
          // using dynamic programming to calculate number of ways you can move in straight line (vertically or horizontally)
          // in s steps and still be inside the island boundaries.
          memset(dp,0,sizeof dp);
          dp[t][i+1] = 1;
          V[0] = 1; VB[0] = (i+1==1) + (i+1==m);
          for (int s=1; s<=N; s++) {
            t = !t;
            for (int a=1; a<=m; a++)
              V[s] += dp[t][a] = (dp[!t][a-1] + dp[!t][a+1]) % mod;
            VB[s] = (dp[t][1] + dp[t][m]) % mod;
            V[s] %= mod;
          }
          memset(dp,0,sizeof dp);
          dp[t][j+1] = 1;
          H[0] = 1; HB[0] = (j+1==1) + (j+1==n);
          for (int s=1; s<=N; s++) {
            t = !t;
            for (int b=1; b<=n; b++)
              H[s] += dp[t][b] = (dp[!t][b-1] + dp[!t][b+1]) % mod;
            HB[s] += (dp[t][1] + dp[t][n]) % mod;
            H[s] %= mod;
          }
          
          // To calculate number of ways you will be at any boundary in s steps
          // let dx be horizontal movement in s steps. we can do that in C[s][dx] ways.
          // H[dx] * VB[s-dx] = number of ways you are inside the island moving horizontally dx times and at the vertical boundary in s-dx vertical movements.
          LL count = 0;
          for(int s=0; s<N; s++) {
            for(int dx=0; dx<=s; dx++) {
              LL t = ((H[dx] * VB[s-dx]) % mod + (HB[dx] * V[s-dx]) % mod) % mod;
              count = (count + (C[s][dx] * t) % mod) % mod;
            }
          }
            
          // Total complexity O(N^2 + N*(m+n))
          return count;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.