Multiple points in line with gaps between - Find minimum max move

Question

We're given a set P of size N, with each element representing a point on the real line. At each of those points p in P, a pile of m(p) stones stones is placed. We want to move the stones such that they're all separated by a minimum distance d, and the goal is to minimize the greatest distance any stone is moved.

Example: there are N = 3 points, and P = {1, 2, 3}. m is defined so that

• At 1, there're two stones (m(1) = 2),
• At 2 there's one stone (m(2) = 1),
• and 3 there're two stones (m(3) = 2).

which can be pictured like so:

      o     o
      o  o  o
 ----------------
...0  1  2  3  4...

If the minimal gap size is 2, then the optimal solution for this example is to

• move one stone from 1 to 0
• move one stone from 1 to -2
• move one stone from 3 to 4
• move one stone from 3 to 6

which gives a solution

    o     o     o     o     o
 ------------------------------
...-2 -1  0  1  2  3  4  5  6...

which means the maximal distance traveled by any stone is 3.

Unfortunately I cannot think of a good way to calculate this number and have yet to find one on the internet! Thank you in advance.

Answer 1

Given a minimal maximal distance x, it is easy to check if there is a valid solution. Start with x = floor(max(m)/2)*d.

For the leftmost point, move x/d stones to the left. If there are less than x/d stones, move all the stones to leftmost possible points (x, x-d etc). If there are more than x/d stones, move them to the right.

For the second leftmost point, move as many points as possible to left and reminder to the right and so on. If at any point, it is not possible to place stones, then x is not valid.

Next step is to perform a binary search for optimal x. If x is an integer you need to repeat this for log(x) times.

Other option is to probably infer the next possible value when there is an impasse. Example: at a given point if there still k stones left without space, probably you need to increase x by at least k/2.