BGL1215 Editorial

PROBLEM LINK:

Practice

Contest

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

SOLUTIONS:

Setter’s Solution
Tester’s Solution

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