Editorial for Wesley's Anger Contest 6 Problem 2 - Cheap Christmas Lights

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

First, we note that toggle operations are commutative so Wesley has the ability to "accumulate" switch usages, such that instead of using one switch per second for the first $i$ ~i~ seconds, he can simply perform $i$ ~i~ switch usages during the $i^\text{th}$ ~i^\text{th}~ second. We then notice that it will take at most $N$ ~N~ seconds to flip all the switches off, since at most $N$ ~N~ lights will be on by the $N^\text{th}$ ~N^\text{th}~ second and Wesley will accumulate up to $N$ ~N~ switch usages by then.

Subtask 1

For the first subtask, we keep track of the state of each light throughout the first $M$ ~M~ seconds, and after the $i^\text{th}$ ~i^\text{th}~ second we check if there are at most $i$ ~i~ lights turned on by iterating through our array storing the lights' states. Be aware that the answer could be greater than $M$ ~M~.

Time Complexity: $\mathcal{O}(N \cdot M)$ ~\mathcal{O}(N \cdot M)~

Subtask 2

Instead of iterating through the array storing lights' states, we can use a counter to keep track of how many lights are on at any given moment. We no longer need to recount the number of lights turned on at every iteration.

Time Complexity: $\mathcal{O}(N + M)$ ~\mathcal{O}(N + M)~

Comments

There are no comments at the moment.