Here's my attempt at a proof:

When : Any one button would turn off all the lights so pick the cheapest one.

Otherwise:

Firstly, we know that each button is either pressed once or not at all because 2 presses is the same as not pressing and is always cheaper since cost is always positive.

Secondly, the order of button presses does not matter as the state of any light is completely determined by the number of button presses at distance away from it.

With that in mind, let's try deciding to press or not press buttons greedily from left to right. Consider that we are at button and all buttons' states have already been decided. At this point all lights will be off otherwise it is impossible to turn off all lights. Now, if light is on, we must press button because no button to the right will be able to turn it off. Likewise, if light is off, we must not press button which will turn it on and we won't be able to turn it off with buttons to the right. So buttons' states can be entirely determined after we know the states of buttons .

Take an arbitrary button press configuration for and let denote pressed buttons in ascending order with . Then the open-closed interval will either be completely on/off and they will be alternating. Remove if is off. Now is on which will be turned off by the th button. Note that this button press flips the entire alternating sequence because its range is while the range of the initial buttons are . This turns on and we can remove and append (like a queue). From there we let induction take over. Note that when would go past the end but it would not cover the end it is impossible to turn off all the lights. From this we see that each contributes and since the contribution would always be positive and we are trying to minimize, we should only press one button .

A better time complexity is instead of like the editorial says because each takes .