Python, Straightforward with Explanation


  • 16

    Let's try for a top-down dp. Suppose we know dp[n][k], the number of permutations of (1...n) with k inverse pairs.

    Looking at a potential recursion for dp[n+1][k], depending on where we put the element (n+1) in our permutation, we may add 0, 1, 2, ..., n new inverse pairs. For example, if we have some permutation of 1...4, then:

    • 5 x x x x creates 4 new inverse pairs
    • x 5 x x x creates 3 new inverse pairs
    • ...
    • x x x x 5 creates 0 new inverse pairs

    where in the above I'm representing any permutation of 1...4 with x's.
    Thus, dp[n+1][k] = sum_{x=0..n} dp[n][k-x].

    This dp has NK states with K/2 work, which isn't fast enough. We need to optimize further.

    Let ds[n][k] = sum_{x=0..k-1} dp[n][x].
    Then dp[n+1][k] = ds[n][k+1] - ds[n][k-n],
    and the left hand side is ds[n+1][k+1] - ds[n+1][k].
    Thus, we can perform all calculations in terms of ds.

    Finally, to save space, we will only store the two most recent rows of ds, using ds and new.

    In the code, we refer to -ds[n][k-n+1] instead of -ds[n][k-n] because the n being considered is actually n+1. For example, when n=2, we are appending information about ds[2][k] to new, so our formula of dp[n+1][k] = ds[n][k+1] - ds[n][k-n] is dp[2][k] = ds[1][k+1] - ds[1][k-1].

    def kInversePairs(self, N, K):
        MOD = 10**9 + 7
        ds = [0] + [1] * (K + 1)
        for n in xrange(2, N+1):
            new = [0]
            for k in xrange(K+1):
                v = ds[k+1]
                v -= ds[k-n+1] if k >= n else 0
                new.append( (new[-1] + v) % MOD )
            ds = new
        return (ds[K+1] - ds[K]) % MOD
    

  • 6

    Haha, all of your posts have the same title..


  • 0
    A
    This post is deleted!

  • 1
    B

    @awice Beautiful solution! I'm having trouble working out the line dp[n+1][k] = ds[n][k+1] - ds[n][k-n+1].

    We have:
    dp[n+1][k]=dp[n][k]+dp[n][k-1]+dp[n][k-2]+...+dp[n][k-n]
    ds[n][k+1]=dp[n][k]+dp[n][k-1]+dp[n][k-2]+...+dp[n][0]
    ds[n][k-n+1]=dp[n][k-n]+dp[n][k-n-1]+dp[n][k-n-2]+...+dp[n][0]

    Doesn't that mean:
    dp[n+1][k] = ds[n][k+1] - ds[n][k-n+1] + dp[n][k-n]? Since the dp[n][k-n] terms is subtracted out by ds[n][k-n+1] and we need to put it back?


  • 0

    @baselRus I edited my post to fix it and clarify the difference, thanks for pointing it out.


  • 1
    B

    @awice That makes sense, thank you.

    C++ version of the algo below.

    Thanks @yangyx for the tip about +MOD in the final line of the solution. Not sure why it's not necessary for Python?

    int kInversePairs(int N, int K) {
            long MOD=pow(10,9)+7;
            vector<long> ds(vector<long>(K+2,1));
            ds[0]=0;
            for (int n=2; n<N+1; n++) {
                vector<long> dsnew(K+2,0);
                for (int k=0; k<K+1; k++) {
                    dsnew[k+1]=(ds[k+1]-(k>=n ? ds[k-n+1] : 0)+dsnew[k])%MOD;
                }
                ds=dsnew;
            }
            return (int)(ds[K+1]-ds[K]+MOD)%MOD;
        }
    

  • 0

    @baselRus In Python, x % y (when y > 0) is guaranteed to be non-negative.


  • 0
    S

    C++ version:

    class Solution {
    public:
    	int kInversePairs(int n, int k) {
    		auto c = std::vector<std::vector<unsigned long long>>(n + 1, std::vector<unsigned long long>(k + 1, 0));
    		auto mod = (int)std::pow(10, 9) + 7;
    		// base case 
    		for (int j = 0; j <= k; j++) {
    			c[1][j] = 0;
    		}
    		c[1][0] = 1;
    		// recursion
    		for (int i = 2; i <= n; i++)
    			for (int j = 0; j <= k; j++) {
    				c[i][j] = ((j - 1 < 0 ? 0 : c[i][j - 1]) +
    					c[i - 1][j] - (j - i < 0 ? 0 : c[i - 1][j - i]) + mod) % mod;
    			}
    		return (int)c[n][k];
    	}
    };

Log in to reply
 

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