Editorial for TLE '17 Contest 5 P2 - Delivery Service II


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

First, note it is always possible to complete all deliveries, so one should never print -1.

For 20\% of the points, we can brute force by trying every single combination of deliveries, checking if they only involve 1 turn, and getting the valid delivery with minimal distance.

Time complexity: \mathcal{O}(D!\times N)

For the next 20\% of the points, we note that only up to 3 points are important: the starting point, the turning point, and the ending point. However, sometimes, there might not be a turning point if all deliveries are headed in the same direction.

Then, for each pair/triple of points, we check if all of the deliveries can be completed, and we take the smallest possible distance.

Time complexity: \mathcal{O}(\max(|x_i|)^3)

The next 20\% was intended to reward those with suboptimal solutions.

For full points, we note that there are two distinct cases: Fax must turn around, or Fax does not turn around. The latter occurs if all deliveries are in the same direction. In this case, we take the absolute difference between the two furthest points.

If Fax must turn around, then we need to decide whether he should head in the positive direction first, or the negative. If Fax heads in the positive direction, he should obviously start with the delivery at the most negative planet heading in a positive direction. Then, he should head all the way to the most positive planet he is required to pick up/drop weapons at, before completing the rest of the deliveries in the opposite direction, stopping as soon as he is finished.

The mirror case is similar.

Time complexity: \mathcal{O}(N+D)


Comments

There are no comments at the moment.