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) :

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++) :
Sample Code (Python) :

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) :

last update: