Codeforces Problem: Magic Power

This problem has two variants:

Variant 1: (Loose constraints, complete problem statement)

Variant 2: (Tighter constraints, requires binary search)

I’m trying to solve the 2nd variant which requires binary search. I tried reading the editorial but didn’t understand much. Could someone explain how exactly we are using binary search here with some code?

Binary search on the answer. Say you want to know how many grams of magic powder is needed to get x cookies. It’s just \sum max(0, xb_i -a_i). xb_i is the amount of this ingredient we need and a_i is how much we already have. If we need more than we have, then we will have to use the magic powder, and the amount needed will be their difference. If you need more than k grams, then you can’t make this many cookies. If you need lesser, you can make at least this many cookies.

1 Like