PROBLEM LINK:Author: AmirReza PoorAkhavan 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 nonnegative.) 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 endpoints 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[j1]$ and $dp2[j]$.
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.
This question is marked "community wiki".
asked 29 Dec '18, 00:16

Could someone please explain what is dp2 and what is its importance? answered 28 Jan, 18:29
