寻找具有L个左可见块和R个右可见块的块排列

1. Introduction

In this tutorial, we’ll see how to compute the number of ways to arrange the blocks with visible blocks on the left and visible ones on the right.

2. Problem Description

There are uniquely-sized blocks whose heights are integers from to . How many ways to arrange the blocks in a row such that exactly blocks are visible from the left and blocks are visible from the right?

A block is visible from the left if there are no longer blocks to the left of it. Similarly, a block is visible from the right if there are no longer blocks to the right of it.

For example, if we arrange blocks with , then the blocks with heights , , and are visible from the left. Also, blocks with heights and are visible from the right:

The longest block with the height of is visible from both sides.

3. Solve the Left Part

Let’s first consider the left part only. Given blocks, let denote the number of ways to arrange them with visible blocks from the left. We can divide this problem into two cases.

For the first case, we place the longest block in the end. In this way, the longest block is always visible from the left no matter how we arrange the rest blocks. Therefore, the problem becomes to solve as we need to find the number of ways to arrange the remaining blocks with visible ones:

For the second case, we place any block other than the longest one in the end. Since the longest block is not at the end position, it hides any blocks right after it, including the last one. Therefore, we should not count the last block as the visible block from the left. To make visible blocks from the left, we have to arrange them on the remaining blocks. Therefore, the problem becomes to solve to arrange the remaining blocks with visible ones:

Since we have possible ways to put a short block into the last position, the total number of ways for the second case is .

Based on the above observations, we can have our recurrence formula:

For the base case, if we have only one block, then there is only one way to see it visible from the left. Therefore, we can have . Also, we have for .

We can use a dynamic programming approach to compute the :

algorithm ArrangeBlocksLeft(N, L):
    // INPUT
    //    N = the total number of blocks
    //    L = the number of visible blocks from the left
    // OUTPUT
    //    Number of ways to arrange N blocks so that L blocks are visible from the left

    Construct a 2-D array dp of size (N+1)x(L+1) with initial values of 0
    dp[1, 1] <- 1

    for n <- 2 to N:
        for l <- 1 to L:
            dp[n, l] <- dp[n - 1, l - 1] + (n - 1) * dp[n - 1, l]

    return dp[N, L]

This algorithm uses a two-dimensional array, , to compute the . The array has rows and columns, as the array index starts from . We use this array to store the computed values. When we compute with bigger and , we can reuse the previously computed results from the smaller numbers.

Firstly, we store the base case, , into the array. Then, we use nested loops to go through all possible and values and compute based on our recurrence formula. After we finish the computing, is the result we want.

Since we have two nested loops over the numbers and , the overall time complexity of this algorithm is .

4. S0lve Both Parts

Let’s consider an arrangement that contains visible blocks from the left and visible blocks from the right. For each visible block, we treat this block and all blocks between it and the next visible block as a whole segment. The longest block is a segment that contains itself only. Also, it is visible from both sides. Therefore, there are segments before the longest block segment and segments after the longest block segments:

For each segment on the right side, we can reverse the order of the blocks and move the whole segment to the left side. This makes segments before the longest block. Also, we can sort these segments based on the highest block in each segment. In this way, we can have visible blocks to the left of the longest block:

Similarly, given a block arrangement where the longest block is at the last position and there are visible blocks from the left, we can pick segments and move them to the right of the longest block. In this way, we can have a block arrangement that contains visible blocks from the left and visible blocks from the right.

Therefore, we can reduce the original problem to a smaller problem that computes the arrangement where the longest block is at the end position and there are visible blocks among the rest blocks, which is .

Also, among the segments, we can choose any segments and move them to the right. Therefore, the overall number of possible ways is , which is also .

We can use a factorial function and the previous function to calculate our result:

algorithm ArrangeBlocks(N, L, R):
    // INPUT
    //    N = the total number of blocks
    //    L = the number of visible blocks from the left
    //    R = the number of visible blocks from the right
    // OUTPUT
    //    The number of ways to arrange N blocks so that
    //    L blocks are visible from the left and R blocks are visible from the right.

    numerator <- Factorial(L + R - 2)
    denominator <- Factorial(L - 1) * Factorial(R - 1)

    return numerator / denominator * ArrangeBlocksLeft(N - 1, L + R - 2)

    // Function to calculate the factorial of a number
    algorithm Factorial(n):
    // INPUT
    //    n = an integer
    // OUTPUT
    //    Returns the factorial of n.
        result <- 1
        for i <- 2 to n:
            result <- result * i
        return result

The time complexity for the factorial functions is . Also, the function takes time. Therefore, the overall time complexity of this algorithm is

5. Conclusion

In this tutorial, we showed a dynamic programming algorithm to compute the number of arrangements for blocks with visible blocks from the left. Based on this algorithm, we can extend to compute the number of arrangements for blocks with visible blocks from the left and visible blocks from the right.