codeforces #333 div 2 D. Lipshitz Sequence

2015年12月23日 作者 CrazyKK

http://codeforces.com/contest/602/problem/D

In order to prove it properly, we’ll consider three numbers Ai, Aj, Ak (i < j < k) and show that one of the numbers L1(i, j),L1(j, k) is  ≥ L1(i, k). W.l.o.g., we may assume Ai ≤ Ak. There are 3 cases depending on the position of Aj relative to Ai, Ak:

• Aj > Ai, Ak — we can see that L1(i, j) > L1(i, k), since |Aj - Ai| = Aj - Ai > Ak - Ai = |Ak - Ai| and j - i < k - i; we just need to divide those inequalities
• Aj < Ai, Ak — this is similar to the previous case, we can prove that L1(j, k) > L1(i, k) in the same way
• Ai ≤ Aj ≤ Ak — this case requires more work:
• we’ll denote d1y = Aj - Ai, d2y = Ak - Aj, d1x = j - i, d2x = k - j
• then, L1(i, j) = d1y / d1x, L1(j, k) = d2y / d2x, L1(i, k) = (d1y + d2y) / (d1x + d2x)
• let’s prove it by contradiction: assume that L1(i, j), L1(j, k) < L1(i, k)
• d1y + d2y = L1(i, j)d1x + L1(j, k)d2x < L1(i, k)d1x + L1(i, k)d2x = L1(i, k)(d1x + d2x) = d1y + d2y, which is a contradiction

We’ve just proved that to any L1 computed for two elements A[i], A[k] with k > i + 1, we can replace one of i, j by a point jbetween them without decreasing L1; a sufficient amount of such operations will give us k = i + 1. Therefore, the max. L1can be found by only considering differences between adjacent points.