Contest Duration: - (local time) (100 minutes) Back to Home
Official

## 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.

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: