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)$ ~\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$ ~\min(F, S) \le F, S~, thus $2 \min(F, S) \le F + S$ ~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$ ~\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)$ ~\mathcal O(\log\sum A_i)~ iterations.

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

Comments

There are no comments at the moment.