Your choice of where to position the first lillipard completely determines the positions of other lilies (since they should all be spaced K distance). For this choice, the cheapest strategy is obvious: keep the lipids in their original order (because any strategy in which two lipids are transferred can be improved without transferring them).
The task is to minimize f(i) , where i is the final position of the first lily, and the function f is the cost of moving all N lilies that will separate from K.
Computing f for a given i is computationally quick - it is just arithmetic (we derive the end positions of each lily from the “no transposition” observation and summarize the differences with the initial positions).
We could minimize f by looking for brute force on all i , but this is likely to be too slow (of course, too slow, since this is a competition of algorithms). Therefore, we need to more intelligently seek space. Binary search? No, not really, because it requires us to know what value we are looking for, and f to be monotonous.
What does f look like? Think about it.
The function f is convex (U-shaped). What for? This follows from our “no transposition” observation. For any choice, I will need to drag some lilies to the right, others to the left. If more lilies need to be dragged right to the left, then we can improve f by moving the empty lily i (and the rest) one step to the right (f will decrease by the difference). Finally, note that the number of lilies that need to be moved to the right is a decreasing function of i, i.e. F ''> = 0. We have proved that f is convex.
Now we look or come up with a (funny) fast binary search algorithm to minimize common convex functions and apply it. Or simply, we can use the bog-standard binary search to solve f '(i) = 0, where f' is the difference between the number of lilies that need to be dragged in each direction.
Remember, before writing any code, solve the problem on paper. Programming is a distraction from thinking about a problem.
def solve(startings, K): N = len(startings) def ends(start): stop = start + N*K endings = range(start, stop, K) assert len(endings) == N return endings def f(start): endings = ends(start) return sum(abs(xy) for (x,y) in zip(startings, endings)) def f_prime(start): endings = ends(start) cost = sum(cmp(x,y) for (x,y) in zip(startings, endings)) return cost lower = min(startings) - N*K upper = max(startings) + N*K g = lambda x: -1 * f_prime(x) stationary_point = binary_search(g, lower, upper) i_best = min(stationary_point, stationary_point + 1, key = f) return f(i_best) def binary_search(f, lower, upper): """Find the greatest integer n, lower <= n <= upper, such that f(n) <= 0. Assumes f is increasing.""" assert upper >= lower assert f(upper) >= f(lower), "f must be increasing" assert f(upper) >= 0 >= f(lower), "f must have a root in range" while upper > lower+1: mid = (upper + lower) // 2 if f(mid) <= 0: lower = mid else: upper = mid return upper if f(upper) <= 0 else lower