TLA - EDITORIAL

general
1

PROBLEM LINKS:

Contest

Practice

DIFFICULTY:

DIFFICULT

EXPLAINATION
Compute the minimum-length path from the starting point where we hold the pen to the last line. On analysis we can breakdown the problem in
the following ways -

  1. The optimum path will be piecewise linear.
  2. The path will be contained in the convex polygon that will contain the starting point and all the end points of the lines.

Now in the given polygon we need to find out the visibility between the different points.
From each point we need to find out the visibility to lines that are below that point. So we can keep track of the sectors from the endpoints to the line below it.
Also we might finish with a perpendicular segment from one line to the last line. So we also need to keep track of visibility from any vertex to finish line.
We can solve this problem by using Dynamic Programming and Meet-in-the-middle.
Dynamic Programming to find out the minimum distance from start to each of the endpoints and the minimum distance of straight segment from any line to the finish line.
Then Meet-in-the-middle to get the minimum between the sum of the DP and the straight path starting on any interval and ending at the last gate.

Expected Complexity - O(n^2)

Reference Solution

Setter Solution

2

Sorry I dont understand the problem statement, nor the solution. If you take x1=x2 for each point, you have something that looks like the travelling salesman problem ? If so, I cannot see how you can achieve O(n^2) complexity…Please explain.