Editorial for Mock CCC '24 Contest 1 S4 - Tommy's Lemonade Stand - Olympiads Online Judge

Editorial for Mock CCC '24 Contest 1 S4 - Tommy's Lemonade Stand

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Tommy_Shan

Let $F_i(x) = -L_ix^2 + S_ix - M_i$ $F_{i} (x) = - L_{i} x^{2} + S_{i} x - M_{i}$ be the flavor rating of the $i^{th}$ $i^{t h}$ recipe with $x$ $x$ mL of water added, $C_i(x) = x$ $C_{i} (x) = x$ be the cost for the $i^{th}$ $i^{t h}$ recipe to add $x$ $x$ mL of water, and $T$ $T$ be the set of indices of the selected recipe.

Essentially, our objective is to find the maximum value of $\frac{\sum_{i=1}^{K}F_{T_i}(x)}{\sum_{i=1}^{K}C_{T_i}(x)}$ $\frac{\sum_{i = 1}^{K} F_{T_{i}} (x)}{\sum_{i = 1}^{K} C_{T_{i}} (x)}$ . We can solve this problem by binary search the answer $mid$ $m i d$ .

$\displaystyle \frac{\sum_{i=1}^{K}F_{T_i}(x)}{\sum_{i=1}^{K}C_{T_i}(x)} \geq mid$ $\frac{\sum_{i = 1}^{K} F_{T_{i}} (x)}{\sum_{i = 1}^{K} C_{T_{i}} (x)} \geq m i d$ $\displaystyle \sum_{i=1}^{K}F_{T_i}(x) \geq mid \times \sum_{i=1}^{K}C_{T_i}(x)$ $\sum_{i = 1}^{K} F_{T_{i}} (x) \geq m i d \times \sum_{i = 1}^{K} C_{T_{i}} (x)$ $\displaystyle \sum_{i=1}^{K}F_{T_i}(x) - mid \times \sum_{i=1}^{K}C_{T_i}(x) \geq 0$ $\sum_{i = 1}^{K} F_{T_{i}} (x) - m i d \times \sum_{i = 1}^{K} C_{T_{i}} (x) \geq 0$ $\displaystyle \sum_{i=1}^{K}F_{T_i}(x) - \sum_{i=1}^{K}(mid \times C_{T_i}(x)) \geq 0$ $\sum_{i = 1}^{K} F_{T_{i}} (x) - \sum_{i = 1}^{K} (m i d \times C_{T_{i}} (x)) \geq 0$ $\displaystyle \sum_{i=1}^{K}(F_{T_i}(x) - mid \times C_{T_i}(x)) \geq 0$ $\sum_{i = 1}^{K} (F_{T_{i}} (x) - m i d \times C_{T_{i}} (x)) \geq 0$ $\displaystyle \sum_{i=1}^{K}(-L_{T_i}x^2 + S_{T_i}x - M_{T_i} - mid \times x) \geq 0$ $\sum_{i = 1}^{K} (- L_{T_{i}} x^{2} + S_{T_{i}} x - M_{T_{i}} - m i d \times x) \geq 0$ $\displaystyle \sum_{i=1}^{K}(-L_{T_i}x^2 + (S_{T_i} - mid)x - M_{T_i}) \geq 0$ $\sum_{i = 1}^{K} (- L_{T_{i}} x^{2} + (S_{T_{i}} - m i d) x - M_{T_{i}}) \geq 0$

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 $0$ $0$ , we can say that $mid$ $m i d$ is possible. Our goal now turns to finding the maximum possible value $mid$ $m i d$ , which can be simply done with binary search.

Observing that to maximize the expression $\sum_{i=1}^{K}(-L_{T_i}x^2 + (S_{T_i} - mid)x - M_{T_i})$ $\sum_{i = 1}^{K} (- L_{T_{i}} x^{2} + (S_{T_{i}} - m i d) x - M_{T_{i}})$ , our strategy is to prioritize the first $K$ $K$ recipes with higher values of $-L_{T_i}x^2 + (S_{T_i} - mid)x - M_{T_i}$ $- L_{T_{i}} x^{2} + (S_{T_{i}} - m i d) x - M_{T_{i}}$ . Additionally, notice that $-L_{T_i}x^2 + (S_{T_i} - mid)x - M_{T_i}$ $- L_{T_{i}} x^{2} + (S_{T_{i}} - m i d) x - M_{T_{i}}$ is a quadratic function in terms of $x$ $x$ , we can find the maximum value of it by find the vertex. Be careful that we should take the $y$ $y$ -intercept instead of the vertex if the vertex have a negative $x$ $x$ value.

Time Complexity: $\mathcal{O}(N\log{N}\log{\frac{1}{\epsilon}})$ $O (N \log N \log \frac{1}{ϵ})$

Comments

There are no comments at the moment.