1866

1866. Number of Ways to Rearrange Sticks With K Sticks Visible (Hard)

There are n uniquely-sized sticks whose lengths are integers from 1 to n. You want to arrange the sticks such that exactly k sticks are visible from the left. A stick is visible from the left if there are no longer sticks to the left of it.

• For example, if the sticks are arranged [1,3,2,5,4], then the sticks with lengths 1, 3, and 5 are visible from the left.

Given n and k, return the number of such arrangements. Since the answer may be large, return it modulo 109 + 7.

 

Example 1:

Input: n = 3, k = 2
Output: 3
Explanation: [1,3,2], [2,3,1], and [2,1,3] are the only arrangements such that exactly 2 sticks are visible.
The visible sticks are underlined.

Example 2:

Input: n = 5, k = 5
Output: 1
Explanation: [1,2,3,4,5] is the only arrangement such that all 5 sticks are visible.
The visible sticks are underlined.

Example 3:

Input: n = 20, k = 11
Output: 647427950
Explanation: There are 647427950 (mod 109 + 7) ways to rearrange the sticks such that exactly 11 sticks are visible.

 

Constraints:

• 1 <= n <= 1000
• 1 <= k <= n

Companies:
Google

Related Topics:
Dynamic Programming

Solution 1. DP

Intuition: A DP problem. For dp(n, k), we have two options, use 1 as the first number or not to use it.

Algorithm:

For dp(n, k):

• If we pick 1 as the first number, we need to use the rest n-1 numbers to get k-1 visible numbers. So this will add dp(n-1, k-1) to the answer
• If we don't pick 1 as the first number, we need to use the rest n-1 numbers to get k visible numbers, i.e. dp(n-1, k) cases. We can put 1 after one of the n-1 numbers so we need to multiply it by n-1. This in total will add dp(n-1, k) * (n-1) cases.

// OJ: https://leetcode.com/problems/number-of-ways-to-rearrange-sticks-with-k-sticks-visible/
// Author: github.com/lzl124631x
// Time: O(NK)
// Space: O(NK)
class Solution {
    long dp[1001][1001] = {}, mod = 1e9 + 7;
    long dfs(int n, int k) {
        if (n < k || k == 0) return 0;
        if (k == n) return 1;
        if (dp[n][k]) return dp[n][k];
        long ans = 0;
        ans = (ans + dfs(n - 1, k - 1)) % mod; // if we pick `1` as the first number, there will be `dp(n - 1, k - 1)` cases
        ans = (ans + dfs(n - 1, k) * (n - 1) % mod) % mod; // if we don't pick `1` as the first number, there will be `dp(n - 1, k) * (n-1)` cases
        return dp[n][k] = ans;
    }
public:
    int rearrangeSticks(int n, int k) {
        memset(dp, 0, sizeof(dp));
        return dfs(n, k);
    }
};

When k == 1, there will be (n-1)! cases. So we can precompute the factorials to save time.

// OJ: https://leetcode.com/problems/number-of-ways-to-rearrange-sticks-with-k-sticks-visible/
// Author: github.com/lzl124631x
// Time: O(NK)
// Space: O(Nk)
long dp[1001][1001] = {}, fact[1001] = {}, mod = 1e9 + 7;
class Solution {
    long dfs(int n, int k) {
        if (n < k) return 0;
        if (k == n) return 1;
        if (k == 1) return fact[n - 1];
        if (dp[n][k]) return dp[n][k];
        long ans = 0;
        ans = (ans + dfs(n - 1, k) * (n - 1) % mod) % mod;
        ans = (ans + dfs(n - 1, k - 1)) % mod;
        return dp[n][k] = ans;
    }
public:
    int rearrangeSticks(int n, int k) {
        memset(dp, 0, sizeof(dp));
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) {
            fact[i] = (fact[i - 1] * i) % mod; // fact(n) = n!
        }
        return dfs(n, k);
    }
};

Solution 2. Bottom-up DP

dp[i][j] = dp[i-1][j-1]  // if we pick 1 as the first number
            + dp[i-1][j] * (i-1) // if we don't pick 1 as the first number
            where i >= j
dp[0][0] = 1
dp[i][j] = 0 if i < j

// OJ: https://leetcode.com/problems/number-of-ways-to-rearrange-sticks-with-k-sticks-visible/
// Author: github.com/lzl124631x
// Time: O(NK)
// Space: O(NK)
class Solution {
public:
    int rearrangeSticks(int n, int k) {
        long mod = 1e9 + 7;
        vector<vector<long>> dp(n + 1, vector<long>(k + 1));
        dp[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= min(i, k); ++j) {
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j] * (i - 1) % mod) % mod;
            }
        }
        return dp[n][k];
    }
};

Since dp[i][j] is only dependent on dp[i-1][j-1] and dp[i-1][j], we can reduce the space complexity from O(NK) to O(K).

// OJ: https://leetcode.com/problems/number-of-ways-to-rearrange-sticks-with-k-sticks-visible/
// Author: github.com/lzl124631x
// Time: O(NK)
// Space: O(K)
class Solution {
public:
    int rearrangeSticks(int n, int k) {
        long mod = 1e9 + 7;
        vector<long> dp(k + 1);
        for (int i = 1; i <= n; ++i) {
            dp[0] = i == 1; // Note that dp[i][0] = 1 only if i == 0; otherwise dp[i][0] = 0.
            for (int j = min(i, k); j >= 1; --j) {
                dp[j] = (dp[j - 1] + dp[j] * (i - 1) % mod) % mod;
            }
        }
        return dp[k];
    }
};