東京大学 情報理工学系研究科 コンピュータ科学専攻 2022年8月実施 専門科目 問題2

Author

zephyr

Description

We consider a division of a set of mutually distinct positive integers into sets , where denotes an empty set. The set sequence is called a division of . We denote by the summation of all the integers in if is a set of integers or a stack consisting of integers. Note that in case is an empty set or an empty stack.

Let for a division of . Let denote the minimum value of among all the possible divisions of into sets.

The following pseudo code shows an algorithm that computes an approximation of . Below, pushes onto the stack , pops the top element of the stack and returns the popped element, and returns the top element of the stack . Note that and return the same value for the same stack , but does not modify the stack.

Answer the following questions.

(1) Calculate .

(2) Show .

(3) Show that holds, regardless of whatever division is chosen in line 2 of the above code.

(4) Show that the while loop in the above code will be repeated at most times, regardless of whatever division is chosen in line 2.

(5) Describe data structures needed to make the above algorithm run in time, and explain how to use them.

---

以下是中文翻译：

我们考虑将一组相互不同的 个正整数 划分为 个集合 ，其中 表示空集。集合序列 称为 的划分。我们用 表示 中所有整数的和，如果 是一个整数集合或由整数组成的堆栈。注意，若 是空集合或空堆栈，则 。

设 为 的划分 。设 为在 所有可能划分 中 的最小值。

下面的伪代码展示了一种计算 近似值的算法。下面， 将 压入堆栈 ， 弹出堆栈 的顶部元素并返回弹出的元素，而 返回堆栈 的顶部元素。注意， 和 为相同堆栈 返回相同的值，但 不会修改堆栈。

回答以下问题。

(1) 计算 。

(2) 证明 。

(3) 证明不论第 2 行选择何种划分 ，。

(4) 证明不论第 2 行选择何种划分 ，上述代码中的 while 循环最多重复 次。

(5) 描述所需的数据结构以使上述算法运行在 时间内，并解释如何使用它们。

Kai

(1)

To find , we need to find the optimal way to divide the set into two subsets such that the maximum subset sum is minimized.

The total sum of the set is:

We need to divide this into two subsets such that the maximum sum is as small as possible. We can consider the following possible divisions:

• :

  • Maximum sum = 9

• :

  • Maximum sum = 10

• :

  • Maximum sum = 11

The minimum maximum sum among these divisions is 9. Therefore:

(2)

Let , and suppose we divide into subsets . By definition:

where is a possible division of into subsets.

For any division , the sum of all elements in must equal the sum of the elements in all subsets:

Let . Then:

because the total sum is distributed across subsets, and the largest subset sum must be at least :

Since is the minimum possible value of , we have:

(3)

The algorithm attempts to balance the largest and smallest subset sums by moving the top element from the stack with the largest sum to the stack with the smallest sum until no improvement can be made.

Let . Initially, each subset in the division has a sum less than or equal to .

When the algorithm moves an element from the subset with the largest sum to the subset with the smallest sum, the maximum possible increase in the smallest sum is bounded by the value of the largest element moved. This adjustment ensures that the final maximum sum in the approximate solution satisfies:

Thus:

(4)

Each iteration of the while loop in the pseudo-code moves an element from the stack (which has the maximum sum) to the stack (which has the minimum sum). Since the total number of elements in all stacks is , and each move reduces the number of elements in by one, the maximum number of iterations cannot exceed . After moves, the stacks have been exhausted of elements that can be moved:

(5)

To achieve an runtime, we can use a priority queue (or a binary heap) for efficiently finding and updating the stacks with the maximum and minimum sums. The steps are as follows:

1. Initialize: Use two priority queues, one for the stack with the maximum sum and one for the stack with the minimum sum.

   • Insert each stack's sum along with its identifier into the respective priority queues. Both insertion and deletion in a priority queue take time.

2. Update: During each iteration of the while loop:

   • Extract the maximum from the "max" priority queue and the minimum from the "min" priority queue.
   • Perform the pop operation from the stack with the maximum sum and push the element onto the stack with the minimum sum.
   • Update the priority queues with the new sums. This step also takes time.

Since each operation inside the while loop is , and the loop runs at most times, the total time complexity of the algorithm is .

Knowledge

贪心算法 集合划分 复杂度分析

重点词汇

• division: 划分
• priority queue: 优先队列
• minmax: 最小最大化

参考资料

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press. Chapter 16: Greedy Algorithms.
2. Kleinberg, J., & Tardos, É. (2005). Algorithm Design. Pearson. Chapter 6: Greedy Algorithms.