Editorial for New Year's '17 P5 - 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.
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 number of consecutive lights desired. Then, you can find the cost of arranging the lights in .
A two pointer approach can be used to reduce the time complexity to just .
Time Complexity: or
Comments