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

标签：

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

Author

zephyr, 祭音Myyura

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) 中展示的算法的平均时间复杂度。

题目描述

设

$$A=\{a_1,a_2,\ldots,a_N\},$$

其中 $1\le a_i\le W$、各元素互异且 $1\le N\le W$。允许对数组执行任意多次（含零次）操作：选择 $1\le i\le N-1$，若

$$a_i+a_{i+1}<W,$$

则交换相邻元素 $a_i,a_{i+1}$。记从 $A$ 可到达的不同数组总数为 $S(A)$，数组最大、最小元素分别记为 $a_h,a_l$（$h,l$ 同时表示其所在位置）。回答：

1. 对 $A=\{4,1,10,3,2\}$，分别求 $W=11$ 与 $W=12$ 时的 $S(A)$。

2. 当 $a_h+a_l<W$ 时，证明

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

   其中 $A-a_l$ 表示删除最小元素后保持其余相对顺序的数组。

3. 当 $a_h+a_l\ge W$ 时，证明

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

   并规定 $S(\varnothing)=1$。

4. 利用第 2、3 问的分解设计从 $A$ 计算 $S(A)$ 的算法。

5. 令 $W=N$，把第 4 问算法的最坏运行时间记为 $T(A)$；假设两元素的加法、比较和复制均耗费单位时间，用 $N$ 表示该最坏复杂度并证明。

6. 仍令 $W=N$，若 $N!$ 种输入排列等概率出现，求该算法的平均时间复杂度。

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+a_i\geq W$ for every other element $a_i$. Hence $a_h$ cannot be swapped and remains at position $h$, dividing $A$ into two independent subarrays. Thus, the total number of distinct arrays is the product of the numbers for the two subarrays:

$$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)

When $W=N$, the $N$ distinct elements in $\{1,\ldots,N\}$ form a permutation of that set. Thus $a_h=N$ and $a_l=1$, so $a_h+a_l\geq W$ and the algorithm always uses the split in (3). A call on $N$ elements takes $\Theta(N)$ time to find the extrema and copy the subarrays. The worst case occurs when $N$ is at an end:

$$T(N)=T(N-1)+\Theta(N).$$

Therefore:

$$\displaystyle T(N)=\Theta\!\left(\sum_{i=1}^N i\right)=\Theta(N^2).$$

(6)

In a uniformly random permutation, the position of the maximum is uniform on $\{1,\ldots,N\}$. Let $\bar T(N)$ be the average running time. Then:

$$\bar T(N) =\frac1N\sum_{h=1}^{N}\bigl(\bar T(h-1)+\bar T(N-h)\bigr)+\Theta(N) =\frac2N\sum_{k=0}^{N-1}\bar T(k)+\Theta(N).$$

This is the standard randomized-quicksort recurrence and gives:

$$\bar T(N)=\Theta(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.