4-6 Monge arrays

An \(m \times n\) array \(A\) of real numbers is a Monge array if for all \(i\), \(j\), \(k\), and \(l\) such that \(1 \le i < k \le m\) and \(1 \le j < l \le n\), we have

\[A[i, j] + A[k, l] \le A[i, l] + A[k, j].\]

In other words, whenever we pick two rows and two columns of a Monge array and consider the four elements at the intersections of the rows and columns, the sum of the upper-left and lower-right elements is less than or equal to the sum of the lower-left and upper-right elements. For example, the following array is Monge:

\[ \begin{matrix} 10 & 17 & 13 & 28 & 23 \\\\ 17 & 22 & 16 & 29 & 23 \\\\ 24 & 28 & 22 & 34 & 24 \\\\ 11 & 13 & 6 & 17 & 7 \\\\ 45 & 44 & 32 & 37 & 23 \\\\ 36 & 33 & 19 & 21 & 6 \\\\ 75 & 66 & 51 & 53 & 34 \end{matrix} \]

a. Prove that an array is Monge if and only if for all \(i = 1, 2, \ldots, m - 1\), and \(j = 1, 2, \ldots, n - 1\) we have

\[A[i, j] + A[i + 1,j + 1] \le A[i, j + 1] + A[i + 1, j].\]

(\(\textit{Hint:}\) For the "if" part, use induction seperately on rows and columns.)

b. The following array is not Monge. Change one element in order to make it Monge. (\(\textit{Hint:}\) Use part (a).)

\[ \begin{matrix} 37 & 23 & 22 & 32 \\\\ 21 & 6 & 7 & 10 \\\\ 53 & 34 & 30 & 31 \\\\ 32 & 13 & 9 & 6 \\\\ 43 & 21 & 15 & 8 \end{matrix} \]

c. Let \(f(i)\) be the index of the column containing the leftmost minimum element of row \(i\). Prove that \(f(1) \le f(2) \le \cdots \le f(m)\) for any \(m \times n\) Monge array.

d. Here is a description of a divide-and-conquer algorithm that computes the leftmost minimum element in each row of an \(m \times n\) Monge array \(A\):

Construct a submatrix \(A'\) of \(A\) consisting of the even-numbered rows of \(A\). Recursively determine the leftmost minimum for each row in \(A'\). Then compute the leftmost minimum in the odd-numbered rows of \(A\).

Explain how to compute the leftmost minimum in the odd-numbered rows of \(A\) (given that the leftmost minimum of the even-numbered rows is known) in \(O(m + n)\) time.

e. Write the recurrence describing the running time of the algorithm described in part (d). Show that its solution is \(O(m + n\log m)\).

a. The "only if" part is trivial, it follows form the definition of Monge array.

As for the "if" part, let's first prove that

\[ \begin{aligned} A[i, j] + A[i + 1, j + 1] & \le A[i, j + 1] + A[i + 1, j] \\\\ \Rightarrow A[i, j] + A[k, j + 1] & \le A[i, j + 1] + A[k, j], \end{aligned} \]

where \(i < k\).

Let's prove it by induction. The base case of \(k = i + 1\) is given. As for the inductive step, we assume it holds for \(k = i + n\) and we want to prove it for \(k + 1 = i + n + 1\). If we add the given to the assumption, we get

\[ \begin{aligned} A[i, j] + A[k, j + 1] & \le A[i, j + 1] + A[k, j] & \text{(assumption)} \\\\ A[k, j] + A[k + 1, j + 1] & \le A[k, j + 1] + A[k + 1, j] & \text{(given)} \\\\ \Rightarrow A[i, j] + A[k, j + 1] + A[k, j] + A[k + 1, j + 1] & \le A[i, j + 1] + A[k, j] + A[k, j + 1] + A[k + 1, j] \\\\ \Rightarrow A[i, j] + A[k + 1, j + 1] & \le A[i, j + 1] + A[k + 1, j] \end{aligned} \]

b.

\[ \begin{matrix} 37 & 23 & \mathbf{24} & 32 \\\\ 21 & 6 & 7 & 10 \\\\ 53 & 34 & 30 & 31 \\\\ 32 & 13 & 9 & 6 \\\\ 43 & 21 & 15 & 8 \\\\ \end{matrix} \]

c. Let \(a_i\) and \(b_j\) be the leftmost minimal elements on rows \(a\) and \(b\) and let's assume that \(i > j\). Then we have

\[A[j, a] + A[i, b] \le A[i, a] + A[j, b].\]

But

\[ \begin{aligned} A[j, a] \ge A[i, a] & (a_i \text{ is minimal}) \\\\ A[i, b] \ge A[j, b] & (b_j \text{ is minimal}) \\\\ \end{aligned} \]

Which implies that

\[ \begin{aligned} A[j, a] + A[i, b] & \ge A[i, a] + A[j, b] \\\\ A[j, a] + A[i, b] & = A[i, a] + A[j, b] \end{aligned} \]

Which in turn implies that either:

\[ \begin{aligned} A[j, b] < A[i, b] & \Rightarrow A[i, a] > A[j, a] \Rightarrow a_i \text{ is not minimal} \\\\ A[j, b] = A[i, b] & \Rightarrow b_j \text{ is not the leftmost minimal} \end{aligned} \]

d. If \(\mu_i\) is the index of the \(i\)-th row's leftmost minimum, then we have

\[\mu_{i - 1} \le \mu_i \le \mu_{i + 1}.\]

For \(i = 2k + 1\), \(k \ge 0\), finding \(\mu_i\) takes \(\mu_{i + 1} - \mu_{i - 1} + 1\) steps at most, since we only need to compare with those numbers. Thus

\[ \begin{aligned} T(m, n) & = \sum_{i = 0}^{m / 2 - 1} (\mu_{2i + 2} - \mu_{2i} + 1) \\\\ & = \sum_{i = 0}^{m / 2 - 1} \mu_{2i + 2} - \sum_{i = 0}^{m / 2 - 1}\mu_{2i} + m / 2 \\\\ & = \sum_{i = 1}^{m / 2} \mu_{2i} - \sum_{i = 0}^{m / 2 - 1}\mu_{2i} + m / 2 \\\\ &= \mu_m - \mu_0 + m / 2 \\\\ & = n + m / 2 \\\\ & = O(m + n). \end{aligned} \]

e. The divide time is \(O(1)\), the conquer part is \(T(m / 2)\) and the merge part is \(O(m + n)\). Thus,

\[ \begin{aligned} T(m) & = T(m / 2) + cn + dm \\\\ & = cn + dm + cn + dm / 2 + cn + dm / 4 + \cdots \\\\ & = \sum_{i = 0}^{\lg m - 1}cn + \sum_{i = 0}^{\lg m - 1}\frac{dm}{2^i} \\\\ & = cn\lg m + dm\sum_{i = 0}^{\lg m - 1} \\\\ & < cn\lg m + 2dm \\\\ & = O(n\lg m + m). \end{aligned} \]

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用