Number of Ways to Rearrange Sticks With K Sticks Visible


Problem

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

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

  • 1n10001 \leq n \leq 1000
  • 1k10001 \leq k \leq 1000

Submit your solution at here

Solution

Intuition

Let’s say we have used up nn sticks labels a1,a2,...,a(n1)a-1,a-2,...,a-(n-1), and we have another stick length ana-n which is smaller than all previous sticks, how can we go from here:

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

Approach

Let f(n,k)f(n,k) denotes the number of ways to arrange nn sticks and only show kk sticks:

  • By that definition, f(0,0)=1f(0,0) = 1, there is 1 way to use nothing and show nothing
  • f(n,k)=f(n1,k1)+(n1)×f(n1,k)f(n,k) = f(n-1,k-1) + (n-1) \times f(n-1,k)

Complexity

  • Time complexity: O(n×k)O(n\times k)
  • Space complexity: O(n×k)O(n\times k), could be further optimized to O(k)O(k) 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;
    }
}