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.