Number of Ways to Rearrange Sticks With K Sticks Visible

Problem

There are uniquely-sized sticks whose lengths are integers from to . You want to arrange the sticks such that exactly 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 and , return the number of such arrangements. Since the answer may be large, return it modulo

Example

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.

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.

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

Submit your solution at here

Solution

Intuition

Let's say we have used up sticks labels , and we have another stick length which is smaller than all previous sticks, how can we go from here:

• From configuration, there is only 1 way can make configuration. That is put the new stick on the front
• From configuration, there are ways to put the new stick behind and keep the number of visible sticks the same

Approach

Let denotes the number of ways to arrange sticks and only show sticks:

• By that definition, , there is 1 way to use nothing and show nothing

Complexity

• Time complexity:
• Space complexity: , could be further optimized to if necessary

Code

impl Solution {
    pub fn rearrange_sticks(n: i32, k: i32) -> i32 {
        let n = n as usize;
        let k = k as usize;
        let INF = 1000_000_007;
        let mut f = vec![vec![0i64; k+1]; n+1];
        // f[i][j] = how many ways to use i stick, and need to make j stick visible
        f[0][0] = 1;
        for j in 1..=k {
            for i in j..=n {
                // put first
                f[i][j] += f[i-1][j-1];
                // put back
                f[i][j] += f[i-1][j]*(i as i64 - 1);
                f[i][j] %= INF;
            }
        }
        return f[n][k] as i32;
    }
}