Problem link: Rocky Bhai
Author: Jeevansh Gagroo
Tester: Tanay Morakhia
Editorialist: Jeevansh Gagroo
DIFFICULTY
Medium-Hard
PREREQUISITES
Basic Programming, Searching and Sorting Techniques
EXPLANATION
Some Observations:
-
There are M trucks and N soldiers and a single soldier can transfer a single crate in a round trip. One needs to find the minimum time under which at least L crates can be transferred from the trucks.
-
To keep the time at a minimum one has to pick the appropriate trucks to transfer the crates from as time varies with each truck. The first array element Ti denotes the time required to transfer the first crate from the i-th truck while the second array element Xi denotes the time needed to transfer the following crates from the i-th truck.
-
For Test Case 1:
There are 3 trucks, 2 soldiers and 5 is the number of needed crates.
Rocky can send the two soldiers to truck 2 and truck 3 having initial crate transfer times as 1 and 2 minutes and 2 and 1 minute as the transfer time for the following crates.
This way, after 3 minutes, (1/1+2/2) crates from 2nd truck and (2/2+1/1) crates from 3rd truck would’ve been transferred and after another minute another crate would get transferred from 3rd truck leading to a total of 5 crates as required.
However, if either of the Soldiers chooses the first truck to transfer the crate from, it would take a total of 5 minutes to transfer the first crate itself which clearly, is slower.
Similar logic applies to the second test case where the 2nd and 3rd trucks, again, are the optimum ones to transfer the crate from.
An approach to this problem would be to find the minimum amount of time to transfer all the crates from a single truck using a single soldier amongst all the trucks and then do a binary search from 0 minutes elapsed to that minimum time while taking into account the initial and follow-up times for other trucks to find the best case where atleast L crates can be transferred, through another function called within the binary search function. As soon as the program comes across such a case, we can output the time required to satisfy it which will be the required minimum time. Similarly, a temporary array can also be built and sorted, which, again, takes into account the initial and follow-up times and stores them in a variable within the binary search to find the minimum time as an alternative approach implemented by the author in their solution.
SOLUTION
C++ Solution: Rocky Bhai C++ Solution
Python Solution: Rocky Bhai Python Solution
Java Solution: Rocky Bhai Java Solution