Editorial for Mock CCC '24 Contest 1 J4/S1 - Magical Magnetic Marbles

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.

Authors: Tommy_Shan, htoshiro

To solve this problem, we aim to minimize the remaining number of marbles after placing K additional marbles into slots. We start by storing the count of empty slots between each pair of adjacent marbles. Then, we adopt a greedy approach to select the maximum number of empty slots intervals, subsequently reducing the total slots in these intervals from the given K. Each interval chosen corresponds to a deduction in the current marble count. Note that this always works because we have the flexibility to insert marbles from left to right.

It's important to note that the input may contain marbles that can merge immediately. Additionally, we need to consider edge cases: when there are no initial marbles, when K is equal to zero, etc....

Time Complexity: \mathcal{O}(N\log{N})


There are no comments at the moment.