Editorial for DMPG '19 G2 - Test Marks
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Observe that the final marks should be a non-decreasing sequence. (The observation was not true for the original problem, which was incorrect as a result.) This is because it never hurts Bob to swap marks and
if
and
, since the
array is non-decreasing.
With this observation, a dynamic programming solution can be found for the first subtask. Let be the most amount of money given that only the first
tests are being considered,
, and
. Then the transition can be done in
by considering the length of marks equal to exactly
. The rest of the marks will definitely be less than
and will contribute to the money earned.
Time Complexity:
For the second subtask, a similar approach is used. Instead of considering the tests from to
, this dynamic programming solution considers the tests from
to
. The advantage here is the dimension
in the first subtask is no longer necessary, as
should always be equal to
. So let
be the most amount of money given that only the last
tests are being considered and
. If
, that is equivalent to adding
to all the marks in the transition. So
Then the transition can be done in .
Time Complexity:
For the final subtask, note that the convex hull optimization can be applied to the dynamic programming solution from the second subtask. This changes the transition into amortized .
Time Complexity:
Comments