×

# DLINE - Editorial

Author: AmirReza PoorAkhavan
Tester: Danial Erfanian
Editorialist: Michael Nematollahi

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.

This question is marked "community wiki".

7★watcher
35
accept rate: 0%

19.8k350498541

 0 Could someone please explain what is dp2 and what is its importance? answered 28 Jan, 18:29 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,683
×2,172
×41

question asked: 29 Dec '18, 00:16

question was seen: 911 times

last updated: 28 Jan, 18:29