Editorial for Yet Another Contest 6 P5 - No More Coyotes - Olympiads Online Judge

Editorial for Yet Another Contest 6 P5 - No More Coyotes

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Josh

Subtask 1

This subtask was reserved for an inefficient implementation of subtask 2.

Time complexity: $\mathcal{O}(N^2)$ $O (N^{2})$

Subtask 2

We can consider each sheep as having two halfplanes. The first halfplane is either $x \le X_i$ $x \leq X_{i}$ or $x \ge X_i$ $x \geq X_{i}$ . The second halfplane is either $y \le Y_i$ $y \leq Y_{i}$ or $y \ge Y_i$ $y \geq Y_{i}$ . Then, the sheep's field of view is the intersection of the two halfplanes.

The key observation is that the rotation move simply toggles one of the two halfplanes of a sheep. This means that the $x$ $x$ and $y$ $y$ axes are actually independent. Thus, only need to solve the simpler problem where every sheep has the position $X_i$ $X_{i}$ , and the field of view $x \le X_i$ $x \leq X_{i}$ or $x \ge X_i$ $x \geq X_{i}$ .

There are only two cases. The first case is where every sheep ends up at the same location. In this case, the fields of the view of the sheep are irrelevant, and all that matters is the positions of the sheep. The total number of moves is easy to calculate, given that it is well known that the optimal final location of the sheep is the median of all positions.

The second case is where there are two distinct final locations of the sheep. Let the final locations of the sheep be $A$ $A$ and $B$ $B$ , with $A < B$ $A < B$ . All of the sheep ending up at $A$ $A$ must have the field of view $x \ge A$ $x \geq A$ , whilst all of the sheep ending up at $B$ $B$ must have the field of view $x \le B$ $x \leq B$ .

Sort the sheep by their original position, breaking ties by prioritising sheep with the field of view $x \ge X_i$ $x \geq X_{i}$ to be earlier in the list. Then, the sheep which end up at $A$ $A$ must form some prefix of the sheep. This optimality can be proven using a simple exchange argument.

Thus it suffices to iterate over all prefixes of the sheep, and maintain the current sum of distances travelled to reach the medians of the prefix and suffix. Don't forget to keep track of the number of rotation moves required. The current sums of distances for both the prefix and suffix can be maintained in multiple different ways, the easiest of which is to notice that when the $i$ $i$ -th sheep is added to the current prefix, the current sum of distances for the prefix increases by $X_i - X_{\lceil \frac{i}{2} \rceil}$ $X_{i} - X_{⌈ \frac{i}{2} ⌉}$ .

Time complexity: $\mathcal{O}(N \log N)$ $O (N \log N)$

Comments

There are no comments at the moment.