BGL1215 Editorial




Author: Pritish Priyatosh Nayak

Tester: Satyabrat Panda

Editorialist: Pritish Priyatosh Nayak




Binary Search


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.


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} ))


Setter’s Solution
Tester’s Solution

pls help me with this prblm i am not able to find solution . I have understood the question