Bike Racing

A bike race is being organised with N bikers. The initial speed and the acceleration of the bikers are given in arrays H[] and A[] respectively. A biker whose speed is L or more is considered to be a fast biker. The total speed on the track for every hour is calculated by adding the speed of each fast biker in that hour. When the total speed on the track is M km/hour or more, the safety alarm turns on. The task is to find the minimum number of hours after which the safety alarm will turn on.

Examples:

Input: N = 3, M = 400, L = 120, H = {20, 50, 20}, A = {20, 70, 90}
Output: 3
Explanation: Speeds of all the Bikers after every hour starting from 0
Biker1 = [20  40  60  80 100] 
Biker2 = [50 120 190 260 330]
Biker3 = [20 110 200 290 380]
Initial Speed on track  = 0 
because none of the biker’s speed is fast enough.
Speed on track after 1st Hour= 120
Speed on track after 2nd Hour= 190+200=390
Speed on track after 3rd Hour= 260+290=550
The Alarm will start at 3rd Hour.

Input: N = 2, M = 60, L = 120, H = {50, 30}, A = {20, 40}
Output: 2

Naive Approach: A simple approach is to calculate the speed of every Bike in every Hour starting from the 0th hour. When the total speed on the track is at least M km/hr, that is the minimum time when the alarm will turn on.

Time Complexity: O(N * max(L, M))
Auxiliary Space: O(1)

Efficient Approach: The problem can be solved with the help of the Binary Search based on the following observation: 

It can be observed that if in ith hour total speed on the track is greater than or equal to M then in (i+1)th hour it will also satisfy the condition as the speed of Bikes are increasing linearly with time.

Follow the steps mentioned below to implement the above idea:

  • Find the maximum and minimum required hours to turn on the alarm because they will be used as the extreme values for the binary search.
  • The maximum and minimum values will be max(L, M) and 0 respectively.
  • Use the binary search over this time range and in each iteration do the following:
    • Iterate from i = 0 to N:
      • Find the speed of the biker at that time.
      • If the speed of the biker at that time is at least L then add his speed to the speed of the track.
    • If the speed of the track is at least M then search on the left half of the time range. Otherwise, search on the right half.
  • Return the minimum time as the answer.

Below is the implementation of the above approach.

C++

  

#include <bits/stdc++.h>

using namespace std;

  

long buzzTime(long N, long M, long L,

              long H[], long A[])

{

    long l = 0, r = 0, mid, sum = 0;

    long x = max(M, L);

  

    

    for (long i = 0; i < N; i++) {

        if ((x - H[i]) % A[i] == 0)

            r = max(r, (x - H[i]) / A[i]);

        else

            r = max(r, (x - H[i]) / A[i] + 1);

    }

  

    

    while (l <= r) {

        mid = (l + r) / 2;

        sum = 0;

  

        

        

        for (long i = 0; i < N; i++)

            if ((H[i] + A[i] * mid) >= L)

                sum += (H[i] + A[i] * mid);

  

        

        

        if (sum >= M)

            r = mid - 1;

        else

            l = mid + 1;

    }

  

    

    return l;

}

  

int main()

{

    long L = 120, M = 400;

    long H[] = { 20, 50, 20 };

    long A[] = { 20, 70, 90 };

    long N = sizeof(H) / sizeof(H[0]);

  

    

    long minHour = buzzTime(N, M, L, H, A);

    cout << minHour;

    return 0;

}

Time Complexity: O(N * log(max(L, M)))
Auxiliary Space: O(1) 

By Julio MarchiPosted on