(a) Suppose we compare the top-right entry A[1][n] of the grid to k. If they are equal, then we are done. Otherwise, for each of the following cases, determine which parts of the grid A definitely cannot contain k. You should provide brief reasoning.
(i) Case 1: A[1][n] > k.
中文翻译 · 本小问
(a) 假设我们将网格右上角元素 A[1][n] 与 k 比较。如果两者相等，任务便已完成。否则，对于以下每种情况，判断网格 A 的哪些部分一定不可能包含 k，并给出简短理由。
(i) 情况 1：A[1][n] > k。
展开共同题干、定义与已给条件（英中对照）
English · 共同题干
A grid is sorted if each of its rows and columns is strictly increasing. For example, the following two-dimensional grid is sorted.
2 3 6 8
4 5 7 10
6 8 9 13
9 11 12 15
Let A[1..n,1..n] be a sorted n × n grid. Given an integer k, our task is to decide if k appears somewhere in A.
中文翻译 · 共同题干
如果一个网格的每一行和每一列都严格递增，我们就称这个网格是有序的。例如，下面的二维网格是有序的：
2 3 6 8
4 5 7 10
6 8 9 13
9 11 12 15
设 A[1..n,1..n] 是一个有序的 n × n 网格。给定整数 k，我们的任务是判断 k 是否出现在 A 的某个位置。
(a) Suppose we compare the top-right entry A[1][n] of the grid to k. If they are equal, then we are done. Otherwise, for each of the following cases, determine which parts of the grid A definitely cannot contain k. You should provide brief reasoning.
(ii) Case 2: A[1][n] < k.
中文翻译 · 本小问
(a) 假设我们将网格右上角元素 A[1][n] 与 k 比较。如果两者相等，任务便已完成。否则，对于以下每种情况，判断网格 A 的哪些部分一定不可能包含 k，并给出简短理由。
(ii) 情况 2：A[1][n] < k。
展开共同题干、定义与已给条件（英中对照）
English · 共同题干
A grid is sorted if each of its rows and columns is strictly increasing. For example, the following two-dimensional grid is sorted.
2 3 6 8
4 5 7 10
6 8 9 13
9 11 12 15
Let A[1..n,1..n] be a sorted n × n grid. Given an integer k, our task is to decide if k appears somewhere in A.
中文翻译 · 共同题干
如果一个网格的每一行和每一列都严格递增，我们就称这个网格是有序的。例如，下面的二维网格是有序的：
2 3 6 8
4 5 7 10
6 8 9 13
9 11 12 15
设 A[1..n,1..n] 是一个有序的 n × n 网格。给定整数 k，我们的任务是判断 k 是否出现在 A 的某个位置。
(b) Hence or otherwise, design an O(n) algorithm that determines whether k appears in A and justify that it is correct.
Hint. After making a query to A[1][n], what are the dimensions of the search space? How could you use that information to construct the algorithm?
中文翻译 · 本小问
(b) 利用上述结论或其他方法，设计一个 O(n) 算法，判断 k 是否出现在 A 中，并说明该算法为什么正确。
原题提示：查询 A[1][n] 后，搜索空间的维度（行数和列数）是多少？你可以如何利用这一信息构造算法？
展开共同题干、定义与已给条件（英中对照）
English · 共同题干
A grid is sorted if each of its rows and columns is strictly increasing. For example, the following two-dimensional grid is sorted.
2 3 6 8
4 5 7 10
6 8 9 13
9 11 12 15
Let A[1..n,1..n] be a sorted n × n grid. Given an integer k, our task is to decide if k appears somewhere in A.
中文翻译 · 共同题干
如果一个网格的每一行和每一列都严格递增，我们就称这个网格是有序的。例如，下面的二维网格是有序的：
2 3 6 8
4 5 7 10
6 8 9 13
9 11 12 15
设 A[1..n,1..n] 是一个有序的 n × n 网格。给定整数 k，我们的任务是判断 k 是否出现在 A 的某个位置。
(c) (Optional) If we instead began by examining the entry in the middle row and middle column [footnote a], what shape does the remaining search space have? How does this make searching in a two-dimensional grid more difficult than the proposed algorithm in part (b)?
Footnote a: or one of the middle rows and columns, if the dimensions are even.
A grid is sorted if each of its rows and columns is strictly increasing. For example, the following two-dimensional grid is sorted.
2 3 6 8
4 5 7 10
6 8 9 13
9 11 12 15
Let A[1..n,1..n] be a sorted n × n grid. Given an integer k, our task is to decide if k appears somewhere in A.
中文翻译 · 共同题干
如果一个网格的每一行和每一列都严格递增，我们就称这个网格是有序的。例如，下面的二维网格是有序的：
2 3 6 8
4 5 7 10
6 8 9 13
9 11 12 15
设 A[1..n,1..n] 是一个有序的 n × n 网格。给定整数 k，我们的任务是判断 k 是否出现在 A 的某个位置。
(a) Our motivation here is to show that once we have moved our hats to l and r respectively, then the only possible pairs of geese that could have height H must be in H. We can show this in the following steps:
(i) Show that if h_l + h_r < H, then every pair in [l,r] that could sum to H is contained in [l+1,r]. That is, excluding goose l from the search space discards no satisfying pairs.
中文翻译 · 本小问
(a) 这里的目标是证明：当两顶帽子分别移动到 l 和 r 后，所有可能使身高之和等于 H 的鹅对，都必须在 H 中。我们可以通过以下步骤证明：
【译注：原文写作 “in H”，但 H 是目标身高；结合后续小问，应理解为候选区间 [l,r] 内。】
(i) 证明：如果 h_l+h_r<H，那么 [l,r] 内每一对身高之和可能等于 H 的鹅都包含在 [l+1,r] 中。也就是说，从搜索空间排除第 l 只鹅，不会丢弃任何满足条件的配对。
展开共同题干、定义与已给条件（英中对照）
English · 共同题干
Suppose we are given an integer H and a set of n geese, where goose l has a positive integer height h_l. You must determine whether there exists a pair of distinct geese i,j (that is, i ≠ j) such that h_l + h_r = H. In the welcome lecture, a binary search algorithm was presented to solve this problem. Now, we will study the two-pointer method.
Consider the algorithm below.
Sort the heights of the geese in non-decreasing order. Put a red hat on the shortest goose and a blue hat on the tallest goose. Then,
• if the hatted geese have total height less than H, move the red hat one space to the right;
• if the hatted geese have total height greater than H, move the blue hat one space to the left; and
• if the hatted geese have total height equal to H, report this pair as the solution.
If a single goose ever has both hats at once, report that there is no solution.
In this problem, we formalise a proof of correctness for the proposed algorithm. Suppose goose l has the red hat and goose r has the blue hat.
Firstly, suppose that there is no pair of geese l < r such that h_l + h_r = H. We claim our algorithm works in this situation. This holds since our algorithm proceeds by replacing l with l + 1, or r with r − 1. Since r − l is a non-negative integer, and at no point does h_l + h_r = H by assumption, eventually l = r. When l = r, one goose is wearing both hats, and the algorithm reports that no such solution exists.
We now wish to show the converse: if there is a pair of geese l < r such that h_l + h_r = H, our algorithm always reports such a pair.
中文翻译 · 共同题干
假设给定整数 H 和一组共 n 只鹅，其中第 l 只鹅的身高 h_l 为正整数。你必须判断是否存在两只不同的鹅 i,j（即 i ≠ j），使 h_l + h_r = H。在欢迎课中，已经介绍过解决这一问题的二分查找算法。现在，我们将研究双指针方法。
【译注：原文先用 i,j 指两只鹅，公式却使用 l,r，此处保留该符号不一致；意思是两只不同鹅的身高之和等于 H。】
考虑下面的算法。
将鹅按身高非递减排序。给最矮的鹅戴上红帽，给最高的鹅戴上蓝帽。然后：
• 如果戴帽子的两只鹅身高之和小于 H，把红帽向右移动一个位置；
• 如果身高之和大于 H，把蓝帽向左移动一个位置；
• 如果身高之和等于 H，报告这一对鹅作为解。
如果两顶帽子在任何时候戴到了同一只鹅头上，则报告无解。
在本题中，我们要为上述算法建立形式化的正确性证明。假设第 l 只鹅戴着红帽，第 r 只鹅戴着蓝帽。
首先，假设不存在满足 l < r 且 h_l + h_r = H 的鹅对。我们声称算法在这种情况下能正确工作。理由是：算法每次将 l 替换为 l+1，或者将 r 替换为 r−1。由于 r−l 是非负整数，而且根据假设，任何时候都不会出现 h_l+h_r=H，因此最终 l=r。当 l=r 时，一只鹅同时戴着两顶帽子，算法便报告不存在这样的解。
现在，我们希望证明反过来的情况：如果存在一对满足 l<r 且 h_l+h_r=H 的鹅，算法就一定会报告这样的一对鹅。
(a) Our motivation here is to show that once we have moved our hats to l and r respectively, then the only possible pairs of geese that could have height H must be in H. We can show this in the following steps:
(ii) Show that if h_l + h_r > H, then every pair in [l,r] that could sum to H is contained in [l,r−1]. That is, excluding goose r from the search space discards no satisfying pairs.
中文翻译 · 本小问
(a) 这里的目标是证明：当两顶帽子分别移动到 l 和 r 后，所有可能使身高之和等于 H 的鹅对，都必须在 H 中。我们可以通过以下步骤证明：
【译注：原文写作 “in H”，但 H 是目标身高；结合后续小问，应理解为候选区间 [l,r] 内。】
(ii) 证明：如果 h_l+h_r>H，那么 [l,r] 内每一对身高之和可能等于 H 的鹅都包含在 [l,r−1] 中。也就是说，从搜索空间排除第 r 只鹅，不会丢弃任何满足条件的配对。
展开共同题干、定义与已给条件（英中对照）
English · 共同题干
Suppose we are given an integer H and a set of n geese, where goose l has a positive integer height h_l. You must determine whether there exists a pair of distinct geese i,j (that is, i ≠ j) such that h_l + h_r = H. In the welcome lecture, a binary search algorithm was presented to solve this problem. Now, we will study the two-pointer method.
Consider the algorithm below.
Sort the heights of the geese in non-decreasing order. Put a red hat on the shortest goose and a blue hat on the tallest goose. Then,
• if the hatted geese have total height less than H, move the red hat one space to the right;
• if the hatted geese have total height greater than H, move the blue hat one space to the left; and
• if the hatted geese have total height equal to H, report this pair as the solution.
If a single goose ever has both hats at once, report that there is no solution.
In this problem, we formalise a proof of correctness for the proposed algorithm. Suppose goose l has the red hat and goose r has the blue hat.
Firstly, suppose that there is no pair of geese l < r such that h_l + h_r = H. We claim our algorithm works in this situation. This holds since our algorithm proceeds by replacing l with l + 1, or r with r − 1. Since r − l is a non-negative integer, and at no point does h_l + h_r = H by assumption, eventually l = r. When l = r, one goose is wearing both hats, and the algorithm reports that no such solution exists.
We now wish to show the converse: if there is a pair of geese l < r such that h_l + h_r = H, our algorithm always reports such a pair.
中文翻译 · 共同题干
假设给定整数 H 和一组共 n 只鹅，其中第 l 只鹅的身高 h_l 为正整数。你必须判断是否存在两只不同的鹅 i,j（即 i ≠ j），使 h_l + h_r = H。在欢迎课中，已经介绍过解决这一问题的二分查找算法。现在，我们将研究双指针方法。
【译注：原文先用 i,j 指两只鹅，公式却使用 l,r，此处保留该符号不一致；意思是两只不同鹅的身高之和等于 H。】
考虑下面的算法。
将鹅按身高非递减排序。给最矮的鹅戴上红帽，给最高的鹅戴上蓝帽。然后：
• 如果戴帽子的两只鹅身高之和小于 H，把红帽向右移动一个位置；
• 如果身高之和大于 H，把蓝帽向左移动一个位置；
• 如果身高之和等于 H，报告这一对鹅作为解。
如果两顶帽子在任何时候戴到了同一只鹅头上，则报告无解。
在本题中，我们要为上述算法建立形式化的正确性证明。假设第 l 只鹅戴着红帽，第 r 只鹅戴着蓝帽。
首先，假设不存在满足 l < r 且 h_l + h_r = H 的鹅对。我们声称算法在这种情况下能正确工作。理由是：算法每次将 l 替换为 l+1，或者将 r 替换为 r−1。由于 r−l 是非负整数，而且根据假设，任何时候都不会出现 h_l+h_r=H，因此最终 l=r。当 l=r 时，一只鹅同时戴着两顶帽子，算法便报告不存在这样的解。
现在，我们希望证明反过来的情况：如果存在一对满足 l<r 且 h_l+h_r=H 的鹅，算法就一定会报告这样的一对鹅。
(b) Using the previous parts, prove that, if there exists a pair of geese l < r such that h_l + h_r = H, then the algorithm eventually reports that such a pair exists.
Suppose we are given an integer H and a set of n geese, where goose l has a positive integer height h_l. You must determine whether there exists a pair of distinct geese i,j (that is, i ≠ j) such that h_l + h_r = H. In the welcome lecture, a binary search algorithm was presented to solve this problem. Now, we will study the two-pointer method.
Consider the algorithm below.
Sort the heights of the geese in non-decreasing order. Put a red hat on the shortest goose and a blue hat on the tallest goose. Then,
• if the hatted geese have total height less than H, move the red hat one space to the right;
• if the hatted geese have total height greater than H, move the blue hat one space to the left; and
• if the hatted geese have total height equal to H, report this pair as the solution.
If a single goose ever has both hats at once, report that there is no solution.
In this problem, we formalise a proof of correctness for the proposed algorithm. Suppose goose l has the red hat and goose r has the blue hat.
Firstly, suppose that there is no pair of geese l < r such that h_l + h_r = H. We claim our algorithm works in this situation. This holds since our algorithm proceeds by replacing l with l + 1, or r with r − 1. Since r − l is a non-negative integer, and at no point does h_l + h_r = H by assumption, eventually l = r. When l = r, one goose is wearing both hats, and the algorithm reports that no such solution exists.
We now wish to show the converse: if there is a pair of geese l < r such that h_l + h_r = H, our algorithm always reports such a pair.
中文翻译 · 共同题干
假设给定整数 H 和一组共 n 只鹅，其中第 l 只鹅的身高 h_l 为正整数。你必须判断是否存在两只不同的鹅 i,j（即 i ≠ j），使 h_l + h_r = H。在欢迎课中，已经介绍过解决这一问题的二分查找算法。现在，我们将研究双指针方法。
【译注：原文先用 i,j 指两只鹅，公式却使用 l,r，此处保留该符号不一致；意思是两只不同鹅的身高之和等于 H。】
考虑下面的算法。
将鹅按身高非递减排序。给最矮的鹅戴上红帽，给最高的鹅戴上蓝帽。然后：
• 如果戴帽子的两只鹅身高之和小于 H，把红帽向右移动一个位置；
• 如果身高之和大于 H，把蓝帽向左移动一个位置；
• 如果身高之和等于 H，报告这一对鹅作为解。
如果两顶帽子在任何时候戴到了同一只鹅头上，则报告无解。
在本题中，我们要为上述算法建立形式化的正确性证明。假设第 l 只鹅戴着红帽，第 r 只鹅戴着蓝帽。
首先，假设不存在满足 l < r 且 h_l + h_r = H 的鹅对。我们声称算法在这种情况下能正确工作。理由是：算法每次将 l 替换为 l+1，或者将 r 替换为 r−1。由于 r−l 是非负整数，而且根据假设，任何时候都不会出现 h_l+h_r=H，因此最终 l=r。当 l=r 时，一只鹅同时戴着两顶帽子，算法便报告不存在这样的解。
现在，我们希望证明反过来的情况：如果存在一对满足 l<r 且 h_l+h_r=H 的鹅，算法就一定会报告这样的一对鹅。
(a) Given an array B of length n, design an O(n log n) algorithm to determine the element that appears most frequently in B, and the indices of B containing that element. You may assume that there is exactly one most common value. Briefly justify your algorithm.
中文翻译 · 本小问
(a) 给定一个长度为 n 的数组 B，设计一个 O(n log n) 算法，找出 B 中出现次数最多的元素，以及 B 中所有包含该元素的下标。你可以假设出现次数最多的值恰好只有一个。简要说明你的算法为什么正确。
展开共同题干、定义与已给条件（英中对照）
English · 共同题干
Let A be an array of n integers. We say that a pair of distinct indices i,j is aligned if their difference is equal to the difference of the values at those indices: A[i] − A[j] = i − j. Let S ⊆ {1,...,n} be a subset of indices. We say that S is an alignment of A if, for all i,j ∈ S such that i ≠ j, i and j are aligned. Our task is to find an alignment of A of maximum size. If there are multiple such alignments, it suffices to find a single one.
For example, consider the array A = [1,4,3,6,5,8,7,1]. One possible alignment here is {2,4,6}. However, note that this is not a maximum alignment.
We will solve this by first solving a simpler problem, and then transforming our original problem into the simpler one.
中文翻译 · 共同题干
设 A 是一个包含 n 个整数的数组。如果两个不同下标 i,j 的差等于这些下标处的数组值之差，即 A[i]−A[j]=i−j，就称这两个下标是对齐的（aligned）。设 S ⊆ {1,...,n} 是一个下标子集。如果对所有属于 S 的不同下标 i,j，i 和 j 都是对齐的，就称 S 是 A 的一个对齐集合（alignment）。我们的任务是找到 A 的一个大小最大的对齐集合。如果存在多个这样的集合，找出任意一个即可。
例如，考虑数组 A=[1,4,3,6,5,8,7,1]。一个可能的对齐集合是 {2,4,6}。但是，请注意它不是最大的对齐集合。
我们将先解决一个更简单的问题，再把原问题转化为这个更简单的问题。
(b) Using the previous part, design an O(n log n) algorithm that finds the maximum alignment of A. Briefly justify your algorithm.
Hint: Transform A into B so that applying the algorithm from (a) solves the problem!
中文翻译 · 本小问
(b) 利用上一小问，设计一个 O(n log n) 算法，找出 A 的最大对齐集合。简要说明你的算法为什么正确。
原题提示：将 A 转换成 B，使得应用 (a) 中的算法就能解决这个问题！
展开共同题干、定义与已给条件（英中对照）
English · 共同题干
Let A be an array of n integers. We say that a pair of distinct indices i,j is aligned if their difference is equal to the difference of the values at those indices: A[i] − A[j] = i − j. Let S ⊆ {1,...,n} be a subset of indices. We say that S is an alignment of A if, for all i,j ∈ S such that i ≠ j, i and j are aligned. Our task is to find an alignment of A of maximum size. If there are multiple such alignments, it suffices to find a single one.
For example, consider the array A = [1,4,3,6,5,8,7,1]. One possible alignment here is {2,4,6}. However, note that this is not a maximum alignment.
We will solve this by first solving a simpler problem, and then transforming our original problem into the simpler one.
中文翻译 · 共同题干
设 A 是一个包含 n 个整数的数组。如果两个不同下标 i,j 的差等于这些下标处的数组值之差，即 A[i]−A[j]=i−j，就称这两个下标是对齐的（aligned）。设 S ⊆ {1,...,n} 是一个下标子集。如果对所有属于 S 的不同下标 i,j，i 和 j 都是对齐的，就称 S 是 A 的一个对齐集合（alignment）。我们的任务是找到 A 的一个大小最大的对齐集合。如果存在多个这样的集合，找出任意一个即可。
例如，考虑数组 A=[1,4,3,6,5,8,7,1]。一个可能的对齐集合是 {2,4,6}。但是，请注意它不是最大的对齐集合。
我们将先解决一个更简单的问题，再把原问题转化为这个更简单的问题。
