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.

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