NONOVSEG - Editorial

PROBLEM LINK:

Practice

Contest

Author: Archit Karandikar

Tester: Jingbo Shang

Editorialist: Utkarsh Saxena

PROBLEM

You are given N given horizontal segments each of length R.
i^{th} segment starts at x_i.
Find out the minimum number of segments you need to move such all segments lie in range [0,L]
and none of them are intersecting.

Constraints: 1 \le N \le 500, 1 \le T \le 2500, 1 \le \sum N \le 2500 and N*R \le L

EXPLANATION

Observation: You can accommodate atmost floor(X/R) segments in a range of length X.

Sort all segments on the x_i.
We will try to find the segments such that fixing them gives the best result.
Remove all segments x_i \lt0 or x_i+R \gt L.
These segments will be moved and cannot contribute to the answer.

Let us define dp[i][j] = maximum number of extra segments that you can accommodate
by fixing exactly j segments among the first i segments.
Assume that the i^{th} segment is also fixed in this state dp[i][j].

In order to calculate this state,
we can brute over all the possible segments that were fixed before the i^{th} segment.
Let k be the second last segment that was fixed.
Range [x_k+R, x_i] is the empty space that is left between the k^{th} and the i^{th} segment.
Length of this extra space X = x_i-x_k-R.
The maximum number of segments that can be accommodated in this extra space = X/R.

dp[i][j] = min(dp[k][j-1] + (x_i-x_k-R)/R) over all k \le i-1.

To answer the original problem:
We can accommodate all the segments in [0,L] without moving j segments
iff there exists an i such that N-j\le dp[i][j].
Find the maximum j that satisfies this condition.

Time Complexity

Space: O(N^2)

Time: O(N^3)

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

1 Like