Editorial for The Christmas Swap


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.

For this problem, binary search the number of consecutive lights you can have. Next, make the observation that the number of operations needed is nondecreasing relative to the amount of consecutive lights desired. Then, you can find the cost of arranging the lights in \mathcal O(N).

A two pointer approach can be used to reduce the time complexity to just \mathcal{O}(N).

Final Complexity: \mathcal{O}(N \log N) or \mathcal{O}(N)


Comments

There are no comments at the moment.