PROBLEM LINKS
DIFFICULTY
EASY
EXPLANATION
A simple greedy solution is possible. First, suppose we have a group of Q coins placed in subsequent cells. How many moves do we need to move this group one cell to the left? The answer is (Q-1)/K+1 (integer division is supposed) – the sum of cells’ indices must decrease by Q while we can only decrease it by K in one move, so that’s the lower bound; moreover, if we move every K-th coin from the left and also the rightmost coin of the group, we’ll make exactly (Q-1)/K+1 moves, so that’s also the upper bound.
Now, consider the rightmost coin (on cell X) and the nearest coin to the left of it (on cell Y). Obviously, we’ll have to move the rightmost coin to cell Y+1 at some moment of time. So why not to do it first? Next, consider the nearest coin to the left of the coin on cell Y (on cell Z). We’ll have to move coins on cells Y and Y+1 to cells Z+1 and Z+2 at some moment of time, so again, why not to do it right now? Here we have two possibilities – either move each coin independently or move them as a group in the sense described above – and it’s easy to see that moving the group is better. Now we have a group of three coins on cells Z, Z+1 and Z+2, so we can move these coins up to the next coin on the left – and again, moving it as a whole group can’t be worse than separating the coins into different groups and moving each of them independently.
So, the optimal strategy is to move from the rightmost coin left increasing the size of the group and moving it one cell left as a whole when needed. This solution is very easy to implement. Its complexity is O(N log N), so it works even when N is up to 100000 and there are 109 cells. The constraints were deliberately set low to allow solutions with higher complexities, but probably the simplest O(N2) solution is harder to implement than the described one.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.