We have the following greedy strategy.

• Among the moves that move a piece to a lower vertex (with a lower value of \(H_i\)), do the one with the smallest maximum potential during and after the move.

Here, the vertices with the same height are assigned some order.

We apply this strategy to the initial and final states in parallel, preferring the move with the smaller maximum potential, until the positions of all pieces become the same between the two states. The answer is the greatest of the maximum potentials we had.

By using priority queues, the complexity of this solution can be \(O(NK\log N)\).

Moreover, by doing some precomputations and moving the pieces on the same vertex at once, we can improve the complexity to \(O(N\log N+K)\).

Validity of the solution:

Let us call a combination of the positions of the pieces a state.

• For a fixed upper limit of the potential, we can see that if applying the greedy strategy to states \(A\) and \(B\) result in the same final state, \(A\) and \(B\) are reachable from each other via that state. Note that transitions are bidirectional.
• For a fixed upper limit of the potential, applying the greedy strategy to states \(A\) and \(B\) result in the same final state if \(A\) and \(B\) are reachable from each other.
  (Proof: the greedy strategy results in the state where each piece is on the lowest vertex reachable. This follows from the fact that each step moves a piece to a position lower than where it is now, and because the position of each piece never gets lower, once a move of a piece becomes available, it never becomes unavailable. Since \(A\) and \(B\) are reachable from each other, the set of reachable vertices for each piece is the same for these two starting states, and so is the final state the strategy results in.)

Thus, for a fixed upper limit of the potential, the greedy strategy results in the same state for the initial and final states if and only if the initial and final states are reachable from each other. If we consider that the aforementioned algorithm fixes the upper limit, tries it, makes it a little bigger, and tries it again, we can see it is valid.