東京大学 新領域創成科学研究科 メディカル情報生命専攻 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 not A:
        return 1

    a_h, a_l = max(A), min(A)
    if a_h + a_l < W:
        return len(A) * compute_S([x for x in A if x != a_l], W)

    h = A.index(a_h)
    return compute_S(A[:h], W) * compute_S(A[h + 1:], W)

assert compute_S([4, 1, 10, 3, 2], 11) == 4
assert compute_S([4, 1, 10, 3, 2], 12) == 10

(5)

Count the work spent scanning and copying array elements. A call on $m$ elements costs $\Theta(m)$ and removes one element. Both branches therefore give the upper bound

$$T(m)\le T(m-1)+O(m)=O(m^2).$$

More explicitly, for a split into sizes $r$ and $m-1-r$, induction uses $r^2+(m-1-r)^2\le(m-1)^2$. For the sorted input $[1,2,\ldots,N]$, both the minimum and maximum are at an end. Every call leaves a single nonempty subarray of size one less, whichever branch applies. Thus the total work is

$$\Theta(N+(N-1)+\cdots+1)=\boxed{\Theta(N^2)}.$$

(6)

Give value $a$ priority $\max(a,N-a)$, breaking a tie in favor of the larger value. The algorithm always removes the element with highest priority in its current subarray. Values $a\ge N/2$ are splitters: their removal divides a subarray into its left and right parts. Values $a<N/2$ are removed without splitting. The priority order starts

$$N,\ N-1,\ 1,\ N-2,\ 2,\ldots.$$

For an element $u$, let $h_u$ be the number of higher-priority splitters, and $L_u$ the number of lower-priority elements. A lower-priority element $v$ is scanned in the call that removes $u$ exactly when none of those $h_u$ splitters lies between $u$ and $v$ in the original permutation. In the random relative order of these $h_u+2$ elements, this occurs precisely when $u,v$ are adjacent, with probability $2/(h_u+2)$.

If $C$ is the sum of the sizes of all recursive subarrays, linearity of expectation gives

$$E[C]=N+\sum_u\frac{2L_u}{h_u+2}.$$

For priority rank $r$ (starting at 1), at least $\lfloor(r-1)/2\rfloor$ preceding elements are splitters. Hence

$$E[C]\le N+\sum_{r=1}^{N} \frac{2N}{\lfloor(r-1)/2\rfloor+2}=O(N\log N).$$

Conversely, consider the $\lfloor N/4\rfloor$ largest values. For the value $N-j$, $0\le j<\lfloor N/4\rfloor$, we have $h_u=j$ and $L_u\ge N/2$. Their contribution alone is

$$E[C]\ge \sum_{j=0}^{\lfloor N/4\rfloor-1}\frac{N}{j+2} =\Omega(N\log N).$$

The average scanning and copying time is therefore $\boxed{\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.