Minimum Distance between Runners before the Race Ends
Given two integers N, K and two arrays speed[] and dist[] each of size N, where speed[i] is the speed of the ith runner and dist[i] is the distance which the ith runner is ahead of the starting line, find the minimum value between the most distant runners at any time if the race ends after K seconds. In other words, we have to tell the minimum distance between the two most distant runners at any time until the race ends.
Examples:
Input: N = 3, speed[] = {1, 2, 3}, dist[] = {1, 2, 3}, K = 3
Output: 2
Explanation: The minimum distance between the two most distant runners will be 2 at time t = 0. As soon as time increases, the distance between the first and the last runner(most distant runners) will keep on increasing.Input: N = 3, speed[] = {1, 2, 3}, dist[] = {3, 2, 1}, K = 3
Output: 0
Explanation: The minimum distance between the two most distant runners will be 0 at time t = 1.
- At time t = 0, dist[] = {3, 2, 1}, distance between most distant runners = 3 – 1 = 2
- At time t = 1, dist[] = {4, 4, 4}, distance between most distant runners = 4 – 4 = 0
- At time t = 2, dist[] = {5, 6, 7}, distance between most distant runners = 7 – 5 = 2
- At time t = 3, dist[] = {6, 8, 10}, distance between most distant runners = 10 – 6 = 4
Approach: To solve the problem, follow the below idea:
The problem can be solved using Ternary Search as the minimum distance between two most distant runners firstly decreases and then increases. The minimum distance between the most distant runners behaves as a Unimodal function, therefore we can apply Ternary Search. So, we can calculate two mid points and calculate the distance between the most distant runners at those two mid points. Now, according to the minimum distance we can reduce the search space. We can initialize the low as 0 and high as K to find the time at which the distance between the most distant runners is minimum. Let f(x) be the minimum distance between two most distant runners at time = x. So,
- If f(mid1) < f(mid2), then hi = mid2.
- If f(mid1) == f(mid2), then lo = mid1 and hi = mid2.
- If f(mid1) > f(mid2), then lo = mid1.
Now, we can keep reducing the search space till hi – lo > 2 and then calculate the answer for time between lo and hi.
Step-by-step algorithm:
- Initialize the search space using lo = 0, hi = K.
- Calculate two mid points, mid1 and mid2 and find the distance between the most distant runners at time = mid1, say dist1 and time = mid2, say dist2.
- If dist1 == dist2
- lo = mid1 and hi = mid2
- Else If dist1 < dist2
- hi = mid2
- Else if dist1 > dist2
- lo = mid1
- Reduce the search space till 300 times to get better precision.
- Return the final answer as the minimum distance between two runners at time = hi or lo.
Below is the implementation of the approach:
C++
#include <bits/stdc++.h> using namespace std; // function to calculate the distance between the most // distant runners at time = mid float f( float mid, int N, int * speed, int * dist) { float minDist = 1e9, maxDist = -1e9; for ( int i = 0; i < N; i++) { float currDist = dist[i] + mid * (speed[i]); minDist = min(minDist, currDist); maxDist = max(maxDist, currDist); } return maxDist - minDist; } // function to calculate the minimum distance between the // most distant runners from t = 0 to t = K float getMinimumDistance( int N, int K, int * speed, int * dist) { float lo = 0, hi = K; // 300 operations are enough for precision int cnt = 300; while (cnt != 0) { cnt--; float mid1 = lo + (hi - lo) / 3.0; float mid2 = hi - (hi - lo) / 3.0; float dist1 = f(mid1, N, speed, dist); float dist2 = f(mid2, N, speed, dist); if (dist1 == dist2) { lo = mid1; hi = mid2; } else if (dist1 < dist2) { hi = mid2; } else { lo = mid1; } } return f(hi, N, speed, dist); } int main() { int N = 3, K = 3; int speed[] = { 1, 2, 3 }, dist[] = { 1, 2, 3 }; cout << setprecision(6) << getMinimumDistance(N, K, speed, dist) << "\n" ; return 0; } |
Java
import java.util.Arrays; public class Solution { // Function to calculate the distance between the most // distant runners at time = mid static float f( float mid, int N, int [] speed, int [] dist) { float minDist = 1e9f, maxDist = -1e9f; for ( int i = 0 ; i < N; i++) { float currDist = dist[i] + mid * speed[i]; minDist = Math.min(minDist, currDist); maxDist = Math.max(maxDist, currDist); } return maxDist - minDist; } // Function to calculate the minimum distance between the // most distant runners from t = 0 to t = K static float getMinimumDistance( int N, int K, int [] speed, int [] dist) { float lo = 0 , hi = K; // 300 operations are enough for precision int cnt = 300 ; while (cnt != 0 ) { cnt--; float mid1 = lo + (hi - lo) / 3 .0f; float mid2 = hi - (hi - lo) / 3 .0f; float dist1 = f(mid1, N, speed, dist); float dist2 = f(mid2, N, speed, dist); if (dist1 == dist2) { lo = mid1; hi = mid2; } else if (dist1 < dist2) { hi = mid2; } else { lo = mid1; } } return f(hi, N, speed, dist); } public static void main(String[] args) { int N = 3 , K = 3 ; int [] speed = { 1 , 2 , 3 }; int [] dist = { 1 , 2 , 3 }; System.out.println(String.format( "%.6f" , getMinimumDistance(N, K, speed, dist))); } } // This code is contributed by shivamgupta0987654321 |
Python3
# function to calculate the distance between the most # distant runners at time = mid def f(mid, N, speed, dist): minDist = 1e9 maxDist = - 1e9 for i in range (N): currDist = dist[i] + mid * speed[i] minDist = min (minDist, currDist) maxDist = max (maxDist, currDist) return maxDist - minDist # function to calculate the minimum distance between the # most distant runners from t = 0 to t = K def get_minimum_distance(N, K, speed, dist): lo = 0 hi = K # 300 operations are enough for precision cnt = 300 while cnt ! = 0 : cnt - = 1 mid1 = lo + (hi - lo) / 3.0 mid2 = hi - (hi - lo) / 3.0 dist1 = f(mid1, N, speed, dist) dist2 = f(mid2, N, speed, dist) if dist1 = = dist2: lo = mid1 hi = mid2 elif dist1 < dist2: hi = mid2 else : lo = mid1 return f(hi, N, speed, dist) if __name__ = = "__main__" : N = 3 K = 3 speed = [ 1 , 2 , 3 ] dist = [ 1 , 2 , 3 ] print ( "{:.6f}" . format (get_minimum_distance(N, K, speed, dist))) # This code is contributed by shivamgupta0987654321 |
C#
using System; public class Solution { // Function to calculate the distance between the most // distant runners at time = mid static float f( float mid, int N, int [] speed, int [] dist) { float minDist = 1e9f, maxDist = -1e9f; for ( int i = 0; i < N; i++) { float currDist = dist[i] + mid * speed[i]; minDist = Math.Min(minDist, currDist); maxDist = Math.Max(maxDist, currDist); } return maxDist - minDist; } // Function to calculate the minimum distance between the // most distant runners from t = 0 to t = K static float GetMinimumDistance( int N, int K, int [] speed, int [] dist) { float lo = 0, hi = K; // 300 operations are enough for precision int cnt = 300; while (cnt != 0) { cnt--; float mid1 = lo + (hi - lo) / 3.0f; float mid2 = hi - (hi - lo) / 3.0f; float dist1 = f(mid1, N, speed, dist); float dist2 = f(mid2, N, speed, dist); if (dist1 == dist2) { lo = mid1; hi = mid2; } else if (dist1 < dist2) { hi = mid2; } else { lo = mid1; } } return f(hi, N, speed, dist); } public static void Main( string [] args) { int N = 3, K = 3; int [] speed = { 1, 2, 3 }; int [] dist = { 1, 2, 3 }; Console.WriteLine( string .Format( "{0:F6}" , GetMinimumDistance(N, K, speed, dist))); } } |
Javascript
// function to calculate the distance between the most // distant runners at time = mid function f(mid, N, speed, dist) { let minDist = 1e9, maxDist = -1e9; for (let i = 0; i < N; i++) { let currDist = dist[i] + mid * speed[i]; minDist = Math.min(minDist, currDist); maxDist = Math.max(maxDist, currDist); } return maxDist - minDist; } // function to calculate the minimum distance between the // most distant runners from t = 0 to t = K function getMinimumDistance(N, K, speed, dist) { let lo = 0, hi = K; // 300 operations are enough for precision let cnt = 300; while (cnt !== 0) { cnt--; let mid1 = lo + (hi - lo) / 3.0; let mid2 = hi - (hi - lo) / 3.0; let dist1 = f(mid1, N, speed, dist); let dist2 = f(mid2, N, speed, dist); if (dist1 === dist2) { lo = mid1; hi = mid2; } else if (dist1 < dist2) { hi = mid2; } else { lo = mid1; } } return f(hi, N, speed, dist); } // main function function main() { let N = 3, K = 3; let speed = [1, 2, 3], dist = [1, 2, 3]; console.log(getMinimumDistance(N, K, speed, dist).toFixed(6)); } main(); |
2
Time Complexity: O(N * logK), where N is the number of runners and K is the duration of the race.
Auxiliary Space: O(1)
Contact Us