Minimize the Maximum Distance between runners
Given two arrays dist[] and speed[] of size N (number of runners) and a positive integer T (duration of a race), where dist[i], speed[i] indicating the initial distance and speed of the ith runner from the starting line respectively. The task is to find the minimum distance between the two most distant runners at any time during the race.
Note: The answer should be correct upto 6 decimal places.
Examples:
Input: T = 2, dist[] = {0, 20}, speed[] = {40, 20}
Output: 0.0
Explanation: Initially, the position of two runners is {0, 20} and after one unit of time, the position of two runners will be {40, 40}. So, the minimum distance between them is 0.Input: T = 1, dist[] = {2, 3}, speed[] = {3, 1}
Output: 0.0
Explanation: Initially, the position of the runners are {2, 3} and within the next one unit of time the two runners have crossed each other and the minimum distance between them would have been 0. So, the answer is 0.0Input: T = 3, dist[] = {2, 3, 7}, speed[] = {2, 2, 1}
Output: 2.0
Explanation: After 3 units of time, the distance between the two most distant runners will be 2 units of distance.
Approach: The problem can be solved using the following approach:
If we observe carefully, the distance between the two most distant runners at any point of time behaves like a unimodal function because the distance between the most distant runners keeps on decreasing until a time X (>=0), and after that the distance keeps on increasing. Since the function is Unimodal, we need to use Ternary Search to find the minimum distance. We will consider 2 points mid1 and mid2 in our search space [0, T] and store the minimum distance between the most distant runners at time mid1 and mid2 in val1 and val2 respectively. Now, we can have 3 cases:
- If val1 == val2, then we can reduce our search space to [mid1, mid2]
- Else if val1 > val2, then we can reduce our search space to [mid1, hi]
- Else if val1 < val2, then we can reduce our search space to [lo, mid2]
Since the error limit is 1e-6 and in each iteration we are reducing our search space by a factor of at least 2/3. Therefore, 200 iterations are sufficient to get our answer.
Step-by-step approach:
- Declare a function solve(mid) that returns the distance between the two most distant runners at time = mid
- Now, initialize the low and high of our search space as 0 and T respectively.
- Find two points mid1 and mid2 and calculate solve(mid1) and solve(mid2)
- Reduce our search space using values of solve(mid1) and solve(mid2) for 200 iterations
- Return the final answer as solve(lo) or solve(hi)
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> #define ll long long int using namespace std; // Function to calculate the distance between the // two most distant runners at time = mid double solve(ll* dist, ll* speed, ll N, double mid) { // Variables to store minimum and maximum distance double minDist = 1e18, maxDist = 0; for ( int i = 0; i < N; i++) { minDist = min(minDist, dist[i] + speed[i] * mid); maxDist = max(maxDist, dist[i] + speed[i] * mid); } return maxDist - minDist; } int main() { ll N = 3, T = 3; ll dist[N] = {2, 3, 7}; ll speed[N] = {2, 2, 1}; double lo = 0, hi = T; // Run 200 iterations to get our answer // correct upto 6 decimal places int cnt = 200; // Ternary Search for the answer while (cnt--) { double mid1 = lo + (hi - lo) / 3.0; double mid2 = hi - (hi - lo) / 3.0; double val1 = solve(dist, speed, N, mid1); double val2 = solve(dist, speed, N, mid2); if (val1 == val2) { lo = mid1; hi = mid2; } else if (val2 > val1) { hi = mid2; } else { lo = mid1; } } cout << fixed << setprecision(6) << solve(dist, speed, N, lo); // your code goes here return 0; } |
Java
import java.util.*; public class Main { public static void main(String[] args) { int N = 3 ; int T = 3 ; int [] dist = { 2 , 3 , 7 }; int [] speed = { 2 , 2 , 1 }; double lo = 0.0 ; double hi = T; int cnt = 200 ; // Perform ternary search to find the optimal time while (cnt-- > 0 ) { double mid1 = lo + (hi - lo) / 3.0 ; double mid2 = hi - (hi - lo) / 3.0 ; double val1 = solve(dist, speed, N, mid1); double val2 = solve(dist, speed, N, mid2); if (val1 == val2) { lo = mid1; hi = mid2; } else if (val2 > val1) { hi = mid2; } else { lo = mid1; } } // Print the result with 6 decimal places System.out.printf( "%.6f" , solve(dist, speed, N, lo)); } // Function to calculate the distance between the two most distant runners at time = mid public static double solve( int [] dist, int [] speed, int N, double mid) { double minDist = 1e18; double maxDist = 0 ; for ( int i = 0 ; i < N; i++) { minDist = Math.min(minDist, dist[i] + speed[i] * mid); maxDist = Math.max(maxDist, dist[i] + speed[i] * mid); } return maxDist - minDist; } } |
Python3
# Function to calculate the distance between the # two most distant runners at time = mid def solve(dist, speed, N, mid): # Variables to store minimum and maximum distance min_dist, max_dist = float ( 'inf' ), 0 for i in range (N): min_dist = min (min_dist, dist[i] + speed[i] * mid) max_dist = max (max_dist, dist[i] + speed[i] * mid) return max_dist - min_dist def main(): N, T = 3 , 3 dist = [ 2 , 3 , 7 ] speed = [ 2 , 2 , 1 ] lo, hi = 0 , T # Run 200 iterations to get our answer # correct up to 6 decimal places cnt = 200 # Ternary Search for the answer while cnt > 0 : mid1 = lo + (hi - lo) / 3.0 mid2 = hi - (hi - lo) / 3.0 val1 = solve(dist, speed, N, mid1) val2 = solve(dist, speed, N, mid2) if val1 = = val2: lo = mid1 hi = mid2 elif val2 > val1: hi = mid2 else : lo = mid1 cnt - = 1 print (f "{solve(dist, speed, N, lo):.6f}" ) if __name__ = = "__main__" : main() |
C#
// C# program for the above approach using System; public class GFG { // Function to calculate the distance between the // two most distant runners at time = mid static double Solve( long [] dist, long [] speed, int N, double mid) { // Variables to store minimum and maximum distance double minDist = double .MaxValue; double maxDist = 0; for ( int i = 0; i < N; i++) { minDist = Math.Min(minDist, dist[i] + speed[i] * mid); maxDist = Math.Max(maxDist, dist[i] + speed[i] * mid); } return maxDist - minDist; } static void Main() { int N = 3, T = 3; long [] dist = { 2, 3, 7 }; long [] speed = { 2, 2, 1 }; double lo = 0, hi = T; // Run 200 iterations to get our answer // correct up to 6 decimal places int cnt = 200; // Ternary Search for the answer while (cnt-- > 0) { double mid1 = lo + (hi - lo) / 3.0; double mid2 = hi - (hi - lo) / 3.0; double val1 = Solve(dist, speed, N, mid1); double val2 = Solve(dist, speed, N, mid2); if (val1 == val2) { lo = mid1; hi = mid2; } else if (val2 > val1) { hi = mid2; } else { lo = mid1; } } Console.WriteLine($ "{Solve(dist, speed, N, lo):F6}" ); } } // This code is contributed by Susobhan Akhuli |
Javascript
// JavaScript code for the above approach: // Function to calculate the distance between the // two most distant runners at time = mid function solve(dist, speed, N, mid) { // Variables to store minimum and maximum distance let minDist = Number.MAX_SAFE_INTEGER; let maxDist = 0; for (let i = 0; i < N; i++) { minDist = Math.min(minDist, dist[i] + speed[i] * mid); maxDist = Math.max(maxDist, dist[i] + speed[i] * mid); } return maxDist - minDist; } const N = 3; const T = 3; const dist = [2, 3, 7]; const speed = [2, 2, 1]; let lo = 0; let hi = T; // Run 200 iterations to get our answer // correct up to 6 decimal places let cnt = 200; // Ternary Search for the answer while (cnt--) { let mid1 = lo + (hi - lo) / 3.0; let mid2 = hi - (hi - lo) / 3.0; let val1 = solve(dist, speed, N, mid1); let val2 = solve(dist, speed, N, mid2); if (val1 === val2) { lo = mid1; hi = mid2; } else if (val2 > val1) { hi = mid2; } else { lo = mid1; } } console.log((solve(dist, speed, N, lo)).toFixed(6)); |
2.000000
Time Complexity: O(N * 2 * log3T) = O(N * log3T), where N is the number of runners and T is the duration of the race.
Auxiliary Space: O(1)
Contact Us