### PROBLEM LINK:

**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.