PROBLEM LINK:
Author: Praveen Dhinwa
Tester: Jingbo Shang
Editorialist: Ajay K. Verma
DIFFICULTY:
Easy
PREREQUISITES:
ad-hoc, basic math
PROBLEM:
Given equal number of red (villager) and blue (dinosaur) points on a straight line (multiple points can share the same location), join each red point with a unique blue point by a line such that the sum of lengths of all lines is minimum.
EXPLANATION:
We first compute the lower bound on the total length on lines, and then show that the lower bound is in fact achievable.
Lower Bound on the Total Length:
Suppose we pick a point p on the line which does not coincide with any of the red or blue points, now let us find out the minimum number of lines that will pass through this point in any arrangement.
Let us say that there are r red points and b blue points on the left of point p, then there can be two cases:
- r >= b. This means we have (r - b) extra red points to the left of p, these points can only be connected to the blue points on the right of p. Hence, there will be at least (r - b) lines that will cross the point p, and will join the blue points on the right of p.
- r < b. In this case at least (b - r) lines will cross the point p, and will join red points on the right of p.
In other words at least |r - b| lines will cross the point p, which is the absolute difference between the red and blue points on the left of p. Now, we can consider all intervals between two consecutive point locations, and find the minimum number of lines containing these intervals.
In the problem we are given an array D[], such that if D[i] is non-negative that means there are D[i] red points at (i, 0), otherwise there are -D[i] blue points at (i, 0).
Now consider the interval between the points (i, 0) and (i + 1, 0). Based on the above observation, it can be seen that there will at least |D[1] + D[2] + … + D[i]| lines crossing this interval (Note that D[i] values are signed, hence their sum computes the difference between red and blue points).
Minimum length of lines = \Sum (minimum number of lines crossing the interval [(i, 0), (i + 1, 0)]), where the sum goes over i from 1 to (N - 1), N being the size of array D.
The following pseudocode can compute this bound in linear time.
int64_t bound(int *D, int N) {
int64_t ans = 0;
int64_t curr = 0;
for (int i from 1 to N) {
curr += D[i];
ans += abs(curr);
}
return ans;
}
Lower Bound is Achievable:
Now we show that the lower bound computed in the above section is in fact achievable.
We use the following strategy to create lines: Start from the leftmost location (1, 0) and create |D[1]| active lines with source either red (if D[i] >= 0), or blue (if D[i] < 0), we extend these active lines to the right. Each time we encounter a location containing red or blue points, we either start more active lines or stop some of the active lines, using the following rules.
- If the active lines have red (blue) sources, and the encountered points are also red (blue), then we start more active lines with source red (blue).
- If the active lines have red (blue) sources, and we encountered blue (red) points, we will close as many active lines as possible by joining them to the encountered blue (red) points (hence, all closed lines will join a red and a blue point). If the number of encountered points is less than the active lines, we will still have active lines with red (blue) source, which will go further right. On the other hand, if the number of blue (red) points is higher than the number of active lines, then all active lines will be closed, and we might need to start new active lines with blue (red) sources, if some of the blue (red) points are unmatched.
It is easy to see that at any point the number of active lines is the absolute difference between the red and blue points encountered, which was in fact the minimum number of lines crossing a point. This means the lower bound is in fact achievable.
Time Complexity:
O (N)
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution will be put up soon.
Tester’s solution will be put up soon.
