algorithms – Minimum number of moves puzzle

Quite simple if time complexity O(K*N) is acceptable:

For each of the N towns, you calculate how long it takes for everyone to reach that town. First, you add everyone’s distance to that town. That’s one minimum requirement. Second, since nobody can do two turns in a row, find the person furthest away. If the person is X steps away, then they can’t reach that town earlier than after 2X-1 moves. So you calculate max (sum of all distances, 2*largest distance – 1). You do that for each town and chose the smallest value.

You can get the time complexitiy a lot lower by counting how many players are in each town initially, calculating the numbers for the first time, and for each of the following towns calculate the numbers in constant time by using the numbers of the previous town. (For example if you know the sum of distances to town 3, then for town 4 you increase that sum by K since everyone goes one step further, then subtract N * number of players in town 4, because these don’t move N steps but no steps at all. )