Editorial for Mock CCC '24 Contest 1 S4 - Tommy's Lemonade Stand
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Let be the flavor rating of the
recipe with
mL of water added,
be the cost for the
recipe to add
mL of water, and
be the set of indices of the selected recipe.
Essentially, our objective is to find the maximum value of . We can solve this problem by binary search the answer
.
Then we can find the maximum value of the expression on the left side of the inequality. If the maximum value is greater than or equal to , we can say that
is possible. Our goal now turns to finding the maximum possible value
, which can be simply done with binary search.
Observing that to maximize the expression , our strategy is to prioritize the first
recipes with higher values of
. Additionally, notice that
is a quadratic function in terms of
, we can find the maximum value of it by find the vertex. Be careful that we should take the
-intercept instead of the vertex if the vertex have a negative
value.
Time Complexity:
Comments