Editorial for DMOPC '21 Contest 2 P1 - Bosses


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: Riolku

Subtask 1

Observe that it is always optimal to grow to our final height at the beginning. Also, note that 0 and the elements of A_i are the only heights we need to consider. The intuitive proof of this is that it is always better to grow more or not to grow at all, depending on H and P.

We can simulate this subtask in quadratic time.

Time Complexity: \mathcal O(N^2)

Subtask 2

We need a faster simulation. Consider a given height x. Let a_c be the number of elements with larger height than x in A. Let a_t be the total height of the elements with larger height than x in A. Then we need to pay Hx to grow to this height, and P(a_t - xa_c) as our potion total. The easiest solution is to insert a zero into the list, sort, and iterate backward.

Time Complexity: \mathcal O(N \log N)

Proof of Claim

Note that since we grow to our final height at the beginning, the order of the bosses is arbitrary. Sort them. As in the second subtask, define a_t and a_c. Consider an arbitrary height x between A_i and A_{i + 1}. While our height is between these two values, a_t and a_c don't choose. Consider our expression of cost from subtask 2 Hx + P(a_t - xa_c):

\displaystyle C = Hx + Pa_t - Pa_cx = (H - Pa_c)x + Pa_t

Depending on how H compares to Pa_c, we either benefit from continually increasing x, or continually decreasing it, until a_t and a_c change.


Comments

There are no comments at the moment.