Explanation for DLINE



Can someone explain the Lunchtime DLINE problem test cases specially the last one from sample input and output.

From the problem statement what I’ve understood is that we have to draw these lines parallel to y-axis, we can move pencil in two ways:

(1) move it towards x axis both +ve and -ve x.

(2) move pencil in +ve y only but first bring it to zero x coordinates.

and 1 unit of time is used to move each changing x and y coordinates, we’ve a limit of time and to draw maximum complete line segments out of these operations.

With this explanation (what I’ve understood) I couldn’t solve the given test cases properly.

Can someone explain it a bit. Just a small Hint or missing point would do the job.

Thank you for your attention.


Holy fuck, I just realized we had to bring the x coordinate to 0 if we have to move the y coordinate. That makes the question a lot easier. Oh no, missed a +200 rating contest :frowning:

Last test case, you have segements [1, 2] and [3, 4] for y = 1, ans same for y = 2.
First you move to y = 1 and then to x = 2, covering 1 line segment. You come back to x = 0. So you’ve now used 1 + 2 + 2 seconds.
Next, move to y = 2, and move to x = 4.
This costs 1 + 4 seconds, and you’ve covered 2 line segments at y = 2.

A little explanation of sample cases wouldn’t have hurt tbh.
Basically, you’ve to start from the bottom and consider which lines to choose and which ones not to choose. I won’t reveal how to do that (or at least that’s what I think would be applied here). Good luck!


@arvindpunk would you mind expanding on the dp part of the solution cause what you said is O(n!) and would only fetch 10 points.


Thanks, I missed it somehow.