PROBLEM LINK:
Author: Pritish Priyatosh Nayak
Tester: Satyabrat Panda
Editorialist: Pritish Priyatosh Nayak
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Binary Search
PROBLEM:
Given N buckets with some capacities. Each turn we can fill 1 bucket with A liters of water and other remaining N-1 buckets with B liters of water and (A>B). Calculate minimum turns to fill/overflow all buckets with water.
EXPLANATION:
Setter approach is to binary search for the answer (the number of turns).
If we were to check whether or not we can fill all buckets in X turns , we can follow the following steps
- Subtract B*X from all buckets, initialize counter to 0.
- For each bucket , having remaining capacity R_i such that R_i >0 , increment counter by \lceil \frac{R_i }{(A-B)} \rceil .
- After iterating over all buckets , if counter value is less than or equal to X, then X is valid and we can fill all buckets in X turns. In such a case , search in the left/lower half of binary search region. Otherwise search in right/upper half of binary search region.
See setter/tester solution for implementation details.
Time Complexity : O(N * log (\frac{max(C)}{B} ))