東京大学 新領域創成科学研究科 メディカル情報生命専攻 2019年8月実施 問題7

标签：

• Tokyo-University
• Constrained-Adjacent-Swap-Reachability-Counting
• Recurrence-Relation-Complexity
• Combinatorial-Probability

Author

zephyr

Description

Let $A = \{a_1, a_2, \ldots, a_N\}$ $(1 \leq a_1, a_2, \ldots, a_N \leq W, a_i \neq a_j \text{ if } i \neq j, 1 \leq N \leq W)$ be an array of size $N$, whose elements are different integers ranging from $1$ to $W$. Let $S(A)$ be the number of all possible distinct arrays each of which can be created by iteratively applying the following operation to $A$, $0$ or more times.

Operation: choose arbitrary $i$ that satisfies $1 \leq i \leq N - 1$ and $a_i + a_{i+1} < W$, and swap the values of $a_i$ and $a_{i+1}$.

We denote the largest number in array $A$ by $a_h$, and the smallest number by $a_l$.

(1) Let $A = \{4, 1, 10, 3, 2\}$. Show $S(A)$ for $W = 11, 12$, respectively.

(2) When $a_h + a_l < W$, prove $S(A) = N \cdot S(A - a_l)$. Here, $A - a_l$ denotes an array that is array $A$ with element $a_l$ removed.

(3) When $a_h + a_l \geq W$, prove $S(A) = S(\{a_1, a_2, \ldots, a_{h-1}\}) \cdot S(\{a_{h+1}, a_{h+2}, \ldots, a_N\})$. Here, we define $S(\emptyset) = 1$.

(4) Show an algorithm that computes $S(A)$ from $A$ using (2) and (3).

(5) Let $W = N$. We define $T(A)$ as the worst time complexity of the algorithm you showed in (4). Write $T(A)$ in terms of $N$, and prove it. You can assume that addition, comparison, copy of two elements take unit time.

(6) Let $W = N$. Assuming that the $N!$ possible permutations have equal probability of being generated as the input array, write the average time complexity of the algorithm you showed in (4).

---

设 $A = \{a_1, a_2, \ldots, a_N\}$ $(1 \leq a_1, a_2, \ldots, a_N \leq W, a_i \neq a_j \text{ 当 } i \neq j, 1 \leq N \leq W)$ 为一个大小为 $N$ 的数组，其元素为 $1$ 到 $W$ 范围内的不同整数。设 $S(A)$ 为可以通过对 $A$ 进行 $0$ 次或多次以下操作创建的所有可能不同数组的数量。

操作：选择满足 $1 \leq i \leq N - 1$ 且 $a_i + a_{i+1} < W$ 的任意 $i$，交换 $a_i$ 和 $a_{i+1}$ 的值。

我们将数组 $A$ 中的最大数记为 $a_h$，最小数记为 $a_l$。

(1) 设 $A = \{4, 1, 10, 3, 2\}$。分别显示 $W = 11, 12$ 时的 $S(A)$。

(2) 当 $a_h + a_l < W$ 时，证明 $S(A) = N \cdot S(A - a_l)$。这里，$A - a_l$ 表示从数组 $A$ 中移除元素 $a_l$ 后的数组。

(3) 当 $a_h + a_l \geq W$ 时，证明 $S(A) = S(\{a_1, a_2, \ldots, a_{h-1}\}) \cdot S(\{a_{h+1}, a_{h+2}, \ldots, a_N\})$。这里，我们定义 $S(\emptyset) = 1$。

(4) 使用 (2) 和 (3) 展示一个从 $A$ 计算 $S(A)$ 的算法。

(5) 设 $W = N$。我们定义 $T(A)$ 为你在 (4) 中展示的算法的最坏时间复杂度。用 $N$ 表示 $T(A)$，并证明它。你可以假设两个元素的加法、比较、复制操作的时间为一个单位时间。

(6) 设 $W = N$。假设 $N!$ 个可能的排列作为输入数组被生成的概率相等，写出你在 (4) 中展示的算法的平均时间复杂度。

Kai

(1)

Given $A = \{4, 1, 10, 3, 2\}$:

For $W = 11$

To find $S(A)$ for $W = 11$, we need to consider the operation condition $a_i + a_{i+1} < W$. We start with the initial array and systematically apply all valid swaps.

Initial array: $\{4, 1, 10, 3, 2\}$

We need to check all possible adjacent swaps under the condition $a_i + a_{i+1} < 11$:

Swap $4$ and $1$ (since $4 + 1 = 5 < 11$):

$$\{1, 4, 10, 3, 2\}$$

Swap $1$ and $4$ back (since $1 + 4 = 5 < 11$):

$$\{4, 1, 10, 3, 2\}$$

Swap $10$ and $3$ (since $10 + 3 = 13 \not< 11$):

$$\text{No swap}$$

Swap $3$ and $2$ (since $3 + 2 = 5 < 11$):

$$\{4, 1, 10, 2, 3\}$$

All valid permutations for $W = 11$ are:

1. $\{4, 1, 10, 3, 2\}$
2. $\{1, 4, 10, 3, 2\}$
3. $\{4, 1, 10, 2, 3\}$
4. $\{1, 4, 10, 2, 3\}$

Therefore, for $W = 11$:

$$S(A) = 4$$

For $W = 12$

For $W = 12$, we need to explore more possible swaps as the condition is more lenient.

Initial array: $\{4, 1, 10, 3, 2\}$

We start with the initial array and apply all valid swaps:

Swap $4$ and $1$ (since $4 + 1 = 5 < 12$):

$$\{1, 4, 10, 3, 2\}$$

Swap $1$ and $10$ (since $1 + 10 = 11 < 12$):

$$\{4, 10, 1, 3, 2\}$$

Swap $3$ and $2$ (since $3 + 2 = 5 < 12$)

$$\{4, 1, 10, 2, 3\}$$

Now explore permutations of $\{1, 4, 10, 3, 2\}$:

Swap $3$ and $2$ (since $3+2=5<12$):

$$\{1, 4, 10, 2, 3\}$$

Now explore permutations of $\{4, 10, 1, 3, 2\}$:

Swap $1$ and $3$ (since $1 + 3 = 4 < 12$):

$$\{4, 10, 3, 1, 2\}$$

Swap $3$ and $2$ (since $3 + 2 = 5 < 12$):

$$\{4, 10, 1, 2, 3\}$$

Now explore permutations of $\{4, 10, 3, 1, 2\}$:

Swap $1$ and $2$ (since $1+2=3<12$):

$$\{4, 10, 3, 2, 1\}$$

Now explore permutations of $\{4, 10, 1, 3, 2\}$:

Similarly, we get:

$$\{4, 10, 2, 3, 1\}, \{4, 10, 2, 1, 3\}$$

Thus, the valid permutations for $W = 12$ are:

1. $\{4, 1, 10, 3, 2\}$
2. $\{1, 4, 10, 3, 2\}$
3. $\{4, 1, 10, 2, 3\}$
4. $\{1, 4, 10, 2, 3\}$
5. $\{4, 10, 1, 3, 2\}$
6. $\{4, 10, 1, 2, 3\}$
7. $\{4, 10, 2, 3, 1\}$
8. $\{4, 10, 2, 1, 3\}$
9. $\{4, 10, 3, 1, 2\}$
10. $\{4, 10, 3, 2, 1\}$

Therefore, for $W = 12$:

$$S(A) = 10$$

(2)

When $a_h + a_l < W$, prove $S(A) = N \cdot S(A - a_l)$.

Given $a_h + a_l < W$, the smallest number $a_l$ can be swapped with any adjacent element and can move to any position in the array.

Therefore, the number of permutations of $A$ is equal to the number of permutations of $A - a_l$, multiplied by the number of possible positions for $a_l$, which is $N$. Hence, we have:

$$S(A) = N \cdot S(A - a_l)$$

(3)

When $a_h + a_l \geq W$, prove $S(A) = S(\{a_1, a_2, \ldots, a_{h-1}\}) \cdot S(\{a_{h+1}, a_{h+2}, \ldots, a_N\})$.

If $a_h + a_l \geq W$, then $a_h$ and $a_l$ , or $a_h$ and any other element of the array, cannot be swapped, effectively dividing $A$ into two independent subarrays. Thus, the total number of distinct arrays is the product of the number of distinct arrays of each subarray:

$$S(A) = S(\{a_1, a_2, \ldots, a_{h-1}\}) \cdot S(\{a_{h+1}, a_{h+2}, \ldots, a_N\})$$

(4)

Algorithm to compute $S(A)$:

def compute_S(A, W):
    if len(A) == 0:
        return 1
	
	# O(N)
    a_h = max(A)
    a_l = min(A)
    
    if a_h + a_l < W:
	    # O(N)
        A_minus_a_l = [x for x in A if x != a_l]
        return len(A) * compute_S(A_minus_a_l, W)
        # T(N-1)
    else:
        index_h = A.index(a_h)
        left_part = A[:index_h]
        right_part = A[index_h+1:]
        return compute_S(left_part, W) * compute_S(right_part, W)
		# 2*T(N/2)

# Example
A = [4, 1, 10, 3, 2]
W = 11
print(compute_S(A, W))  # Output: 4
W = 12
print(compute_S(A, W))  # Output: 10

(5)

Given that the worst-case scenario involves removing the smallest element each time, the time complexity can be analyzed as follows:

1. Initial size: $N$
2. Operation: Finding the smallest element (which takes $O(N)$ time) and removing it, reducing the problem size by 1.
3. Recurrence relation: The total time complexity is the sum of the times taken for each step as we reduce the size of the array from $N$ to 0.

The time complexity can be expressed as:

$$T(N) = N + (N-1) + (N-2) + \ldots + 1$$

This is the sum of the first $N$ natural numbers:

$$T(N) = \sum_{i=1}^{N} i = \frac{N(N+1)}{2}$$

Therefore, the worst-case time complexity is:

$$T(N) = O(N^2)$$

(6)

Assuming that each of the $N!$ permutations of the array is equally likely, and given that the average scenario does not always involve removing the smallest element each time, the time complexity will be different.

In the average case, the algorithm will involve both scenarios of removing the smallest element and splitting the array. However, the average number of operations will not always hit the worst-case scenario.

Considering the balanced approach where the split operation happens frequently, the recurrence relation can be described more favorably compared to the worst-case:

$$T_{\text{avg}}(N) = 2T(N/2) + O(N)$$

Using the Master Theorem for $a = 2$, $b = 2$, and $f(N) = O(N)$:

$$T_{\text{avg}}(N) = O(N \log N)$$

Thus, the average time complexity is:

$$T_{\text{avg}}(N) = O(N \log N)$$

Knowledge

组合计数 递归 复杂度分析 主定理

解题技巧和信息

1. Recursive Reduction: Understand how reducing a problem by removing an element or splitting the array affects complexity.
2. Complexity Analysis: Sum of first $N$ numbers is $\frac{N(N+1)}{2}$.
3. Master Theorem: Useful for solving recurrence relations in divide-and-conquer algorithms.

重点词汇

• worst-case 最坏情况
• average-case 平均情况
• time complexity 时间复杂度
• recurrence relation 递推关系

参考资料

1. Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, Chapter 4.