## Editorial for IOI '16 P3 - Shortcut

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

**Subtasks 1 and 2:** try to connect every pair of stations on the main line and then find the *diameter* by checking every pair of stations. In Subtask 2 you have to precompute the stations coordinates along the main line . These values will be used in all solutions for the other subtasks.

**Subtasks 3 and 4:** we can try to connect every pair of stations on the main line and then find the resulting diameter. To find the diameter, we can write down the resulting cycle and then iterate through it, keeping a pointer to the opposite position on the cycle (opposite in terms of distance). We also can maintain two queues for each of the halves, keeping the furthest stations in terms of cycle distance plus secondary line length. This will help us to compute the diameter in time, making the solution run in time in total. In subtask 3, we can use some data structures instead of queues, making the solution run in . However, both solutions are technically complex.

**Subtask 5:** This subtask requires some clever ideas. First, we can do binary search on the answer. Then, we have to somehow check if it's possible to make the diameter less or equal to some fixed value . Let's write some inequations.

Let's allow the express line to start and end not only on the stations, but also on arbitrary points and on the main line. We use the same coordinate system that was used to compute .

If we take a look at some pair and , we can see that if then all pairs of and work. Otherwise, only and such that are valid. This formula actually describes a square rotated . What we need to do is to try all pairs of and , cross corresponding squares and then check if there is some point where and inside the resulting area.

So far we can just check for such a point by trying all possible pairs of and . However, there is a nice way to perform this check in linear time and not care about its impact on the overall complexity in future. Proceed with a sweep line and keep two pointers: on the lowest point above the square and highest point below the square. Since functions of both positions from the -coordinate of the sweep line are unimodal, the overall complexity will be .

The total complexity of such a solution is where is the maximal possible answer.

**Subtask 6:** Now, two more observations are needed. Let's fix and . Now the pair produces some square iff . Let's fix and find the intersection of the squares for all possible . The bounds of the square produced can be rewritten as follows:

We can see that the bounds only depend on and . We need only maximal and minimal values of and , so we can use some data structure, for example, segment tree, to find them in time. The total complexity of this solution is .

**Subtasks 7 and 8:** Notice that is equal to . It follows that if we iterate through in the order of increasing then the set of that is used to take minimum and maximum values is only expanding, i.e. once some particular is in the set, it remains there for all remaining values of . Thus, we can keep current maximum and minimum values of and without any data structure with the use of the two pointers technique and two sorted arrays. The total complexity of the full-score solution is . Note, that sorting is done at the very beginning and there is no need to re-sort these two arrays in each iteration of binary search.

Another approach to achieve this time bound that doesn't use sort (and thus solves the decision problem itself in linear time) is to get rid of useless elements. We say that station dominates station if . Now, if one station is dominated by the other we can consider only the dominator as the endpoint of the express line (unless the position being dominated is considered for the other end). The set of positions that are not dominated by any other index can be found in linear time by computing prefix and suffix maximums. Now when we use the same solution as for subtask 6, but we query maximum and minimum values for inequality only when considering "good" positions (not dominated by any other positions). This allows us to achieve the situation that the query bound moves only right and we can process each of them in .

## Comments