Intuition

The calculated max_moves = M represents the peak requirement imposed by either a single machine needing to unload its excess or a single boundary needing a certain net flow. Since M moves provide enough capacity to meet this peak requirement, and moves can be coordinated to address both needs simultaneously, M moves are sufficient to ensure all machines reach the target state.

The primary driver for moves is often to correct imbalances between sections of the machine line. The balance_k value represents the net number of dresses that must eventually move from the left section (0…k) to the right section (k+1…n-1) (if balance_k > 0) or vice-versa (if balance_k < 0).

The core requirement is to achieve a net flow of balance_k dresses across boundary k over the entire process. We know that abs(balance_k) <= M.

A machine with a deficit doesn’t create a bottleneck by itself in the same way an excess does. It doesn’t need to perform a minimum number of “give” actions. Instead, it needs dresses to arrive. The constraint shifts from the machine itself to the flow required to reach it, i.e., The impact of the deficit is measured via the boundary/flow bottleneck, not the machine excess bottleneck.

Pseudo code for the optimal action plan


# balance(0,0) = 0
# balance(0,n) = 0

for round in range(0, M): #M is the max of max bottlenecks
 next_round_state = machines[:]
 for i in range(0, n): # N is the number of machines
   if machine[i] > 0 
	if balance(0, i) < 0:
	   next_round_state[i] = machine[i] - 1 	
	   next_round_state[i - 1] = machine[i - 1] + 1 	
        else if balance(i+1, n) < 0:
	   next_round_state[i] = machine[i] - 1 	
	   next_round_state[i + 1] = machine[i + 1] + 1 	

 machines = next_round_state

When M > max(machines)

i.e., M = abs(balance(0, j)) for a TBD j

Around j the machine balances must looks like {… surplus at j1, 0,…, 0, deficit at j2,…}, and j >= j1 + 1 and j <= j2. Otherwise, abs(balance(0, j)) is not maximum. Therefore, we can definitely pass one dress from left to right at j1,…,j2 - 1, and thus M = abs(balance(0,j)) is reduced by 1 after this round

When M == max(machines)

assuming machines[k] = max(machines) for a TBD k

Claim A: balances(0, k) <= 0 and balances (k+1, n) <= 0 Proof: by contradiciton, then if balance(0, k) > 0 and balances(k+1, n) <= 0, then balance(0, k+1) > M which contradicts with M’s definition that it is the max of abs(balance(0, i)) over all Is

Claim B: balance(0, k) < 0 or balances(k+1, n) < 0. Could be both at the same time Proof: by contradiciton, if both >= 0, then balances(0, n) > 0, which contradicts that the all machines will have the same number of dresses eventually

Claim C: when balance(0, k) < 0 and balance(k+1, n) = 0, then machines[k-1] < M Proof: By contradiciton, assume machines[k-1] = M. At least one dress will be moved from k to k - 1. then abs(balance(0, k-1)) > abs(balance(0, k)) = M, this contradicts that M is also the max of abs(balance(i))

Claim D: when balance(0, k) = 0 and balance(k+1, n) < 0, then machines[k+1] < M Proof: similar to proof of claim C, just in a mirrored direction

Claim E: when balance(0, k) < 0 and balance(k+1, n) < 0, machines[k -1] < M or machines[k+1] < M Proof: By contradiction, proof is a combination of D & E

With claim C ,D, and E, we can prove that when M == max(machines), there is always a move that moves M to a neighboring machine with fewer dresses, that is, M is reduced by 1 after this round

When M < max(machines)

TODO