E - Transformable Teacher Editorial by evima
Let teacher’s height be fixed, and let \(h_0, h_1, \dots, h_N\) be the heights of teacher and children, sorted in the increasing order. Then, it is optimal to make pairs of \((h_0, h_1), (h_2, h_3), \dots, (h_{N-1}, h_N)\).
Proof
Let us assume that, in a optimal combination of pairs, $h_0$ is not paired with $h_1$, and there are two pairs $(h_0, x)$ and $(h_1, y)$. Then, $|h_0 - x| + |h_1 - y| \geq |h_0 - h_1| + |x - y|$, so we can exchange the pair make pairs $(h_0, h_1), (x, y)$ instead. Since $(h_0, h_1)$ are paired, we can exclude $h_0, h_1$ and apply the same discussion recursively, in order to prove that $(h_0, h_1), (h_2, h_3), \dots, (h_{N-1}, h_N)$ are optimal.Therefore, by sorting \(H\) and, for every form \(w\), inserting \(w\) to the proper position in \(H\), the problem can be solved in a total of \(O(NM+N\log N)\) time.
However, this answer is TLE.
Sammple Code (Python) : https://atcoder.jp/contests/abc181/submissions/17733459
However, by storing the cumulative sums of \(|H_{2i-1}-H_{2i}|\) and \(|H_{2i}-H_{2i+1}|\), you do no longer spend \(O(N)\) time for insertions and summation, and the problem can be solved in a total of \(O((N + M) \log N + M \log M)\) time.
Sample Code (C++) : https://atcoder.jp/contests/abc181/submissions/17734513
Sample Code (Python) : https://atcoder.jp/contests/abc181/submissions/17733390
You can also solve the problem by sorting \(W\) firsthand and using sliding window, storing the spans where \((H_{2i-1},H_{2i})\) are paired and the spans where \((H_{2i},H_{2i+1})\) are paired, and the sum of differences of heights for each of those spans.
Sample Code (Python) : https://atcoder.jp/contests/abc181/submissions/17733416
posted:
last update: