Hi,
I would like to share an alternate solution to the Codeforces problem The Meeting Place Cannot Be Changed. My solution is in Java, but it can be translated to other languages. I enjoyed solving this problem.
This problem is in fact very similar to the LeetCode problem Peak Index in a Mountain Array.
The official solution does binary search on the minimum time needed for the friends to meet, but my solution does binary search on the optimal place to meet.
How do we do binary search if the positions are non-integers? We simply multiply each coordinate by 10^6, then find the optimal time for integer meeting points, then divide by 10^6. This will ensure that the difference between the meeting place returned and the actual meeting place is \leq 10^{-6}, and the difference between the minimum times is \leq 10^{-6}.
My solution relies on the two following key observations:
- The minimum times to meet every spot on the line decreases, then increases as you sweep the line.
- No three points contain the same minimum times.
The minimum time for each meeting place is the maximum times it takes for each friend to travel to that meeting place. We can compute the minimum time for an arbitrary meeting place in O(n) time.
Now, we can do binary search on the optimal meeting place while keeping track of the minimum time. For each meeting place \text{mid} we check, we find the minimum times for it and adjacent meeting places, and compute the total running minimum of all times. We break out of the search if \text{minTime(mid - 1)} > \text{minTime(mid)} < \text{minTime(mid + 1)}; otherwise, we use the information to narrow the bound of possible optimal meeting places.
Once we break out of the loop, we have the minimum meeting time and hence the answer.
My code below:
import java.io.*;
import java.util.*;
public class TheMeetingPlaceCannotBeChanged {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int numFriends = Integer.parseInt(in.readLine());
// positions multiplied by 10^6 so we can work with integers
long[] positions = new long[numFriends];
StringTokenizer stp = new StringTokenizer(in.readLine());
for (int i = 0; i < numFriends; i++) {
positions[i] = Long.parseLong(stp.nextToken()) * 1000000L;
}
int[] speeds = new int[numFriends];
StringTokenizer sts = new StringTokenizer(in.readLine());
for (int i = 0; i < numFriends; i++) {
speeds[i] = Integer.parseInt(sts.nextToken());
}
// Find min, max position
long minPosition = Long.MAX_VALUE;
long maxPosition = Long.MIN_VALUE;
for (long p : positions) {
minPosition = Math.min(minPosition, p);
maxPosition = Math.max(maxPosition, p);
}
// Binary search to find minimum time
long low = minPosition;
long high = maxPosition;
double minTime = Double.MAX_VALUE;
while (low <= high) {
long mid = (low + high) / 2;
double midTime = time(positions, speeds, mid);
double lowerTime = time(positions, speeds, mid - 1);
double higherTime = time(positions, speeds, mid + 1);
minTime = Math.min(Math.min(minTime, midTime), Math.min(lowerTime, higherTime));
if (midTime < lowerTime && midTime < higherTime) break;
else if (lowerTime > midTime || midTime > higherTime) {
low = mid + 1;
} else {
high = mid - 1;
}
}
System.out.printf("%.6f\n", minTime / 1000000);
}
// Time is maximum time of all friends to get to point
static double time(long[] positions, int[] speeds, long position) {
double maxTime = Double.MIN_VALUE;
for (int i = 0; i < speeds.length; i++) {
maxTime = Math.max(maxTime, (double) Math.abs(positions[i] - position) / speeds[i]);
}
return maxTime;
}
}
Thanks,
rayfish
.