Official

E - Pancakes Editorial by evima

First, let us observe the change caused by a reversion to the tower and its ugliness:

As seen in this figure:

  1. Inside the reversed segment, the total difference of sizes does not change, since they just get reversed.
  2. Outside the reversed segment, the total difference of sizes does not change.
  3. At both ends of the reversed segment, the differences of sizes do change.

Thus, when evaluating the change in the ugliness caused by a reversion, we only need to consider the changes at both ends of the reversed segment. For example, in the figure above, the ugliness changes from \(17\) to \(13\) because the differences at both ends of the reversed segment change from \(6, 3\) to \(4, 1\).

More specifically, we can calculate the change in the ugliness as follows.

Basically, the ugliness decreases by \(|A_{l-1} - A_l| + |A_r - A_{r+1}| - |A_{l-1} - A_r| - |A_l - A_{r+1}|\), because the difference at the left end changes from \(|A_{l-1} - A_l|\) to \(|A_{l-1} - A_r|\) and the right end changes from \(|A_r - A_{r+1}|\) to \(|A_l - A_{r+1}|\).

However, it is slightly different if \(l = 1\) or \(r = N\), as follows.

  • If \(l = 1\) and \(r \neq N\): the ugliness decreases by \(|A_r - A_{r+1}| - |A_l - A_{r+1}|\), since there is no pancake at the left end.
  • If \(l \neq 1\) and \(r = N\): the ugliness decreases by \(|A_{l-1} - A_l| - |A_{l-1} - A_r|\), since there is no pancake at the left end.
  • If \(l = 1\) and \(r = N\): the ugliness does not change, since the whole tower just gets reversed.

Now, for each choice of \(l, r\), we can find the resulting ugliness in constant time, but we have no time to try all \(O(N^2)\) choices. Let us find a more efficient way to find the optimal choice.

As we seen above, the change in the ugliness depends only on the sizes of the four pancakes at both ends of the reversed segment: \(A_{l-1}, A_l, A_r, A_{r+1}\). Let us consider the correlation between their magnitude relation and the change in the ugliness.

As shown below, there are six possible magnitude relations between \(A_{l-1}, A_l, A_r, A_{r+1}\), when we do not distinguish two relations that are the same after flipping one of them horizontally, vertically, or both. The yellow part marks the differences in sizes of pancakes, which contribute to the difference in the ugliness.

Which of these six patterns decrease the ugliness?

  • In patterns 1 and 2, both yellow parts get longer, so the ugliness increases.
  • In patterns 3 and 4, one of the yellow parts gets shorter, but the other gets longer by the same amount, so the ugliness does not change.
  • In patterns 5 and 6, both yellow parts get shorter, so the ugliness decreases.

Thus, the ugliness decreases in patterns 5 and 6. Additionally, it decreases by the length of the intersection of the two yellow parts, multiplied by \(2\).

Let us sort out our findings:

If \(A_{l-1} \lt A_l\) and \(A_r \lt A_{r+1}\):

  • If the segment \(A_{l-1} \leq x \leq A_l\) and the segment \(A_r \leq x \leq A_{r+1}\) have an intersection, the ugliness decreases by its length multiplied by \(2\).

If \(A_{l-1} \gt A_l\) and \(A_r \gt A_{r+1}\):

  • If the segment \(A_l \leq x \leq A_{l-1}\) and the segment \(A_{r+1} \leq x \leq A_r\) have an intersection, the ugliness decreases by its length multiplied by \(2\).

If neither of the above holds, the ugliness does not decrease.

Thus, to maximize the decrease in the ugliness, we need to choose \(l, r\) with the longest intersection. Now, let us consider the following problem:

Problem: Longest Intersection

You are given \(M\) segments; the \(i\)-th segment is \(L_i \leq x \leq R_i\). You will choose two of them. Find the maximum possible length of the intersection of the chosen segments. If no two segments have an intersection, your answer should be \(0\).

If we can solve this problem, we can find the answer as follows:

  • Find \(Z_1\), the Longest Intersection among all the segments \(A_i \leq x \leq A_{i+1}\) for all positions where \(A_i \lt A_{i+1}\).
  • Find \(Z_2\), the Longest Intersection among all the segments \(A_{i+1} \leq x \leq A_i\) for all positions where \(A_i \gt A_{i+1}\).
  • Then, the maximum possible decrease for the case \(l \neq 1, r \neq N\) is \(\max(2Z_1, 2Z_2)\). For the case \(l = 1\) or \(r = N\), we can try all possible choices, since there are not many of them.

Now, what remains is to solve Longest Intersection.

We will describe one way to solve Longest Intersection in \(O(M \log M)\) time.

The intersection of Segment \(i\), \(L_i \leq x \leq R_i\), and Segment \(j\), \(L_j \leq x \leq R_j\), is \(\max(L_i, L_j) \leq x \leq \min(R_i, R_j)\). We want to find \(i, j\) that maximize its length.

Now, let us sort \(L_i\) and assume \(L_1 \leq L_2 \leq \cdots \leq L_M\). Then, the intersection of Segments \(i, j\) \((i \lt j)\) is \(L_j \leq x \leq \min(R_i, R_j)\). Thus, for a fixed \(j\), the length of the intersection is maximized by choosing the \(i\) with the maximum \(R_i\). For example, in the figure below, the optimal choice for \(j = 4\) is \(i = 2\) (resulting in the intersection \(L_4 = 25 \leq x \leq 48 = R_2\)), and the optimal choice for \(j = 7\) is \(i = 5\) (resulting in the intersection \(L_7 = 37 \leq x \leq 65 = R_7\)).

Therefore, the following algorithm finds the Longest Intersection:

  1. Sort the \(M\) segments in ascending order of \(L_i\).
  2. For each \(j = 2, 3, \cdots, M\), in this order, compute the longest intersection when \(j\) is fixed to that value: \(L_j \leq x \leq \min(R_j, \max(R_1, R_2, \dots, R_{j-1}))\).
  3. The answer is the longest of all those intersections, or \(0\) if there is no such intersection.

Here, we can cumulatively find the values \(\max(R_1, R_2, \dots, R_{j-1})\), so the bottleneck of this algorithm is sorting, resulting in the complexity of \(O(M \log M)\).

Summary of the solution:

  1. The change in ugliness depends only on the two ends of the reversed segment, and is \(|A_{l-1} - A_l| + |A_r - A_{r+1}| - |A_{l-1} - A_r| - |A_l - A_{r+1}|\) (when \(2 \leq l \lt r \leq N-1\)).
  2. The ugliness decreases only when \(A_{l-1} \lt A_l\) and \(A_r \lt A_{r+1}\), or \(A_{l-1} \gt A_l\) and \(A_r \gt A_{r+1}\), by the length of the intersection of the segment with endpoints \(A_{l-1}\) and \(A_l\) and the segment with endpoints \(A_r\) and \(A_{r+1}\), multiplied by \(2\).
  3. If we separately deal with the case \(A_i \lt A_{i+1}\) and the case \(A_i \gt A_{i+1}\), our objective is to find the longest intersection of two segments chosen from \(M\) segments.
  4. We can find the longest intersection in \(O(M \log M)\) time. One way to do this is to sort the segment in ascending order of \(L_i\), the left end.

This solution solves the problem in \(O(N \log N)\) time.

Sample Implementation:

Bonus: Can you maximize the ugliness of the tower, in \(O(N)\) time?

posted:
last update: