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

A straightforward solution is to use prefix sum arrays.

**Time Complexity:**

##### Alternate Solution

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

Note that , thus . That is, the total number of people remaining is at most half the number of people remaining on the previous day.

We start with people, and on the final day end with at least 1 person, so there are at most iterations.

**Time Complexity:**

## Comments