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
    

Log in to reply
 

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