Editorial for IOI '15 P1 - Boxes with Souvenirs - Olympiads Online Judge

Editorial for IOI '15 P1 - Boxes with Souvenirs

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.

The problem has a solution in linear time. The solution is basically greedy, and it is based on several observations. Discovering only a subset of those observations usually leads to a correct but slower solution.

We will use the word trip to denote the part of a solution between two visits to a warehouse. The numbering of locations increases in the CW direction. (Imagine the circle as a clock face with the warehouse at $12 = 0$ $12 = 0$ , and locations at $1$ $1$ through $11$ $11$ .)

Clearly, in an optimal solution, we will never go twice along the same segment in the same direction during the same trip – any such trip can be shortened while still visiting the same set of locations. The moment when we deliver boxes also does not matter. WLOG we may assume that we deliver a box we want the first time we visit its location. Hence, we can divide the trips into three groups:

CW trips: The boxes are delivered while going CW, and we return by going CCW.
CCW trips: The same with directions reversed.
Full-circle trips: The entire circle is traversed once in either direction.

Also, we may easily note that each CW/CCW trip must end at one of the boxes we leave in that trip – going any farther can be skipped.

Lemma 1 In an optimal solution, the distance traveled CW in a CW trip is at most $\frac l 2$ $\frac{l}{2}$ (half of the circle). The same holds for CCW trips.

The proof is trivial: if you travel more than $\frac l 2$ $\frac{l}{2}$ while delivering the boxes and now you want back, it is cheaper to continue in the same direction than to return – i.e., to make a full-circle trip instead.

Lemma 2 There exists an optimal solution satisfying the property from Lemma 1 where in each trip, we deliver a contiguous subset of boxes (i.e., boxes with no other box located between them).

Proof: Consider any optimal solution.

First of all, note that in each half of the circle, the boxes that are delivered during full-circle trips are all at least as far from the warehouse as the boxes delivered in CW/CCW trips.

This is because we could take the farthest box delivered in a CW/CCW trip and swap it for one that is closer but delivered in a full-circle trip. The full-circle trip will remain the same length, the CW/CCW trip will now be shorter, which contradicts the optimality of the original solution.

Now we know that the set of boxes delivered by all full-circle trips is contiguous. As we can pick any of them during each full-circle trip, we can easily plan the full-circle trips so that each of them delivers a contiguous subset of these boxes.

Now let us look at the boxes delivered during the CW trips. Obviously, the $k$ $k$ farthest from the warehouse can be delivered in the same trip – this can be proved using a switching argument similar to the one above. QED.

Lemma 3 There is always an optimal solution with at most one full-circle trip. Additionally, we deliver exactly $k$ $k$ boxes during that trip (or all of them if $n < k$ $n < k$ ).

Proof: It always makes sense to drop as many boxes as we can during a full-circle trip, because we can move boxes from CW/CCW trips to full-circle trips at no cost.

As we already know, there is an optimal solution in which each trip drops a contiguous segment of boxes. For any partition of boxes into contiguous segments, at most one such segment contains boxes on both sides of the circle. Only that one segment needs to be delivered in a full-circle trip, for each other segment of boxes, a CW/CCW trip is at most as expensive as a full-circle one.

Theorem 4 The problem can be solved in $\mathcal O(n)$ $O (n)$ time.

Proof: Let $l_i$ $l_{i}$ be the optimal distance to deliver the first $i$ $i$ boxes in the CW direction using CW trips. These values can be precomputed in $\mathcal O(n)$ $O (n)$ time. Let $r_i$ $r_{i}$ be the same values for the CCW direction.

There may be no full-circle trip. In $\mathcal O(n)$ $O (n)$ , try all possibilities for how many boxes are delivered in CW trips. (This is overkill but the benefit is that we do not have to handle boxes opposite the warehouse as a special case.) Look for the minimum of $l_i+r_{n-i}$ $l_{i} + r_{n - i}$ .

There may be one full-circle trip. Again in $\mathcal O(n)$ $O (n)$ , try all possibilities for the $k$ $k$ boxes delivered during such a trip. Look for the minimum of $l_i+l+r_{n-k-i}$ $l_{i} + l + r_{n - k - i}$ . Return the minimum of all those values.

Another proof: If there are fewer than $k$ $k$ boxes in the location opposite the warehouse, there are clearly $\mathcal O(k)$ $O (k)$ different possibilities for the segment delivered during a full-circle trip, and $\mathcal O(k)$ $O (k)$ possibilities to consider if there is no full-circle trip.

If there are $k$ $k$ or more boxes in the location opposite the warehouse, there is an optimal solution with no full-circle trip. Additionally, we can obviously assume that less than $k$ $k$ of those boxes are delivered in CW trips. This gives us, again, $\mathcal O(k)$ $O (k)$ possibilities for the split between boxes delivered in either direction.

In either case, we have $\mathcal O(k)$ $O (k)$ possibilities to try. For each of those $\mathcal O(k)$ $O (k)$ possibilities, we can compute the optimal total cost without any precomputation: we simply go through the locations of the remaining boxes with step $k$ $k$ and add those distances up. Thus, each possibility can be evaluated in $\mathcal O(\frac n k)$ $O (\frac{n}{k})$ , which gives a total time complexity of $\mathcal O(n)$ $O (n)$ again.

Comments

There are no comments at the moment.