PROBLEM LINK:
Author: AmirReza PoorAkhavan
Tester: Danial Erfanian
Editorialist: Michael Nematollahi
PREREQUISITES:
DP
QUICK EXPLANATION:
Define dp[j][i] as the minimum time required to draw i of the given line segments whose y coordinate is less than or equal to j. Go through all possible y coordinates in order starting from 0. For each y coordinate choose how many of the line segments with that y coordinate you want to choose. Update the dp based on that.
EXPLANATION:
Let’s observe what an optimal solution would look like.
First, in an optimal solution, we won’t choose to draw a line segment if there is a line segment to its left (with the same y coordinate) that we haven’t drawn yet. The reason is that to draw such a line segment, we must move over all the line segments to its left to reach it. So it doesn’t make sense to not draw those line segments that we’ve moved over. This means that for each y coordinate, we should choose a prefix of line segments with that y coordinate to draw. (Note that the line segments don’t intersect; so we can order them. Also, note that all coordinates are non-negative.)
Second, in an optimal solution, we don’t draw a line segment b before a line segment a if the y coordinate of b is greater than a. This observation is derived from the fact that we can only change our y coordinate if our x coordinate is equal to 0.
We’ll use these two observations to come up with a dynamic programming solution that is as follows:
Let’s define dp[j][i] as the minimum time required to draw i of the given line segments whose y coordinate is less than or equal to j. Similarly, let’s define dp2[j][i] as the minimum time required to draw i of the given lines whose y coordinate is less than j and then go to point (0, j). These dp arrays can be calculated as follows:
First, let’s add the end-points of the line segments whose y coordinate is equal to z to vec[z] and then sort vec[z]. Then with the following code we can update dp[j] and dp2[j+1] from dp[j-1] and dp2[j].
for (int i = 0; i <= n; i++) dp[j][i] = dp[j-1][i];
for (int i = 0; i <= n; i++) dp2[j+1][i] = dp2[j][i] + 1;
//choosing how many line segments with y coordinate equal to j we'll pick
for (int t = 1; t <= (int)vec[j].size(); i++)
//updating dp[j][i] and dp2[j+1][i]
for (int i = t; i <= n; i++) {
dp[j][i] = min(dp[j][i], dp2[j][i-t] + vec[j][t-1]);
dp2[j+1][i] = min(dp2[j+1][i], dp2[j][i-t] + vec[j][t-1]*2 + 1);
}
This solution’s time complexity is O(\sum_{j=0}^{MAXY} vec[j].size() \times N) which is equal to O(N \times N).
The described solution takes O(N^2) space, but note that we always only need the last two rows of the arrays. Hence, we can keep only them and the required space would be reduced to O(N). To see the described solution with O(N) space, refer to the editorialist’s code. In the code, dp[0] corresponds to our dp here and dp[1] corresponds to dp2 here.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here
Tester’s solution can be found here
Editorialist’s solution can be found here.