Editorial for DMOPC '20 Contest 1 P2 - Victor's Moral Dilemma


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

A straightforward solution is to use prefix sum arrays.

Time Complexity: \mathcal O(N + D)

Alternate Solution

A more interesting question would be "why does brute force pass?"

Note that \min(F, S) \le F, S, thus 2\min(F, S)\le F + S. That is, the total number of people remaining is at most half the number of people remaining on the previous day.

We start with \sum A_i people, and on the final day end with at least 1 person, so there are at most \mathcal O(\log\sum A_i) iterations.

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


Comments

There are no comments at the moment.