Although the official solution is indeed correct, it lacks reasonable explanation on the solution page and doesn\'t show convictively why it works. Almost all the posts in discussion only give the code implementation and/or mere explanation of **how** the code processes the input rather than **why**. There are only 2 posts that point out it: [Formal-proof-of-the-solution](https://leetcode.com/problems/super-washing-machines/discuss/591578/Formal-proof-of-the-solution), and [Follow-up:-What-if-the-question-require-detailed-operation-for-each-step](https://leetcode.com/problems/super-washing-machines/discuss/216790/Follow-up%3A-What-if-the-question-require-detailed-operation-for-each-step). (Unfortunately, the proof in the former post is incorrect.)\n\nThe solution essentially only tells the lower bound of the total number of moves, without touching on the reachability of this lower bound at all. One could ask a follow-up question like \'How do you go about a detailed movement procedure that costs the minimum possible number of moves?\'. This post is going to give you the guarantee that this lower bound is in fact reachable for any input.\n\nLet\'s make some assumptions first to ignore the trivial cases:\n* Assume *n* >= 2, and *n* is a divisor of the total number of dresses (i.e. answer is not -1);\n* Assume the list `machines` is already normalized by deducting `avg` to have an average of zero;\n* Assume the values in `machines` are not all zeros (i.e. there exist at least one positive and one negative in `machines`).\n\nThere are totally *n*-1 demarcation lines that can split all the machines into two groups - group on the left and group on the right. We need a variable to denote these demarcation lines. Let `D` be a list of length *n*-1. `D[i]`(i=0, ..., n-2) represents the line that stands between `machines[i]` and `machines[i+1]` thus split all machines into two groups: `machines[0]`, ..., `machines[i]` on the left, and `machines[i+1]`, ..., `machines[n-1]` on the right hand. The value stored in `D[i]` stands for the number of essential transfer(s) that must take place across this line. If the transfer(s) need to be from left to right(i.e. from `D[i]` to `D[i+1]`), we make `D[i]` be positve; otherwise if the transfer(s) need to be from right to left(i.e. from `D[i+1]` to `D[i]`) we make `D[i]` be negative. For example, for `machines` = [-4, -4, 7, 1], `D` = [-4, -8, -1]; for `machines` = [3, -2, -1], `D`= [3, 1].\n

\n\n\nIt is easy to see that `max{abs(D)}` is the lower bound of the final answer. However this lower bound is not tight enough. For example, for `machines` = [-2, 5, -3], `D` = [-2, 3]. The minimum number of moves for this input is actually 5 rather than 3. The reason is that each machine can only pass at most one dress at each step.\n\nLet `M` = `max{abs(D), machines} = max{max{abs(D)}, max{machines}}`. We claim that `M` is the minimum number of moves, which is exactly what the official solution claims. The following part of the article is going to prove that the lower bound `M` is actually reachable for any valid input list `machines`.\n\nWe will conduct the proof by constructing a specific movement policy and showing that after each time step the updated `M` corresponding to the resulting `machines` list is one less than the former one. \n\nOne more notation: let `L[i]` denote the number of dresses that machine *i* need to pass to its left neighbor (can be negetive); and `R[i]` denote the number of dresses that machine *i* need to pass to its right neighbor. It is obvious that `L[i] = -D[i-1]` (i=1, ..., n-1); and `R[i] = D[i]` (i=0, ..., n-2).\n\n**We design the movement policy as below:**\n```\n# At each time step, do the following:\nmachines_updated = machines.copy()\nfor i in range(n):\n\tif machines[i] >= 0:\n\t\tif i > 0 and L[i] > 0:\n\t\t\t# move one dress from machine i to machine i-1\n\t\t\tmachines_updated[i] -= 1\n\t\t\tmachines_updated[i-1] += 1\n\t\telif i < n-1 and R[i] > 0:\n\t\t\t# move one dress from machine i to machine i+1\n\t\t\tmachines_updated[i] -= 1\n\t\t\tmachines_updated[i+1] += 1\nmachines = machines_updated # used for the subsequent time step\n```\nAlthough the above procedure is written as a *for* loop, it represents all operations that we do at only one single time step. (i.e. all the operations inside the *for* loop can be performed simultaneously.)\n\nAnother thing to note is that we won\'t come across the situation where there is not enough dress in the current machine to pass to its neighbor, because `machines[i]` >= 0 means machine i has at least `avg` dresses left, and for each machine we will move at most one dress out of it.\n\nThen we provide several lemmas which are helpful for the final proof.\n\n***Lemma 1.*** After each time step, for every 0 <= *i* <= n-2, the `D_updated[i]` (corresponding to `machines_updated`) is no more than its previous value `D[i]`. More precisely, `D_updated[i]` is either `D[i]` or `D[i]-1`.\n(The proof of Lemma 1 is left to readers, which is fairly easy. Hint: for each demarcation line, there is at most one dress passed across this line at each time step.)\n\n***Lemma 2.*** If `machines[i] > 0`, at least one of `L[i]` and `R[i]` is positive.\n\nFollowing *Lemma 2*, it is easy to derive *lemma 3*:\n***Lemma 3.*** For any `machines[i] >= 0`(i.e. if old value no less than `avg`), `machines_updated[i] <= machines[i]`, more precisely, `machines_updated[i]` is either `machines[i]` or `machines[i]-1`.\n\nThe above lemmas ensure that by following the above procedure, after each time step, `M_updated = max{max{abs(D_updated)}, max{machines_updated}}` is no more than its previous value `M` (`M_updated` is either `M` or `M - 1`). Then we are going to show that `M_updated` is definitely equal to `M - 1`.\n\n***Lemma 4*** If there exists a machine i s.t. `machines[i] = M`, then both `L[i]` and `R[i]` is non-negative, and at least one of `L[i]` and `R[i]` is positive. \n(*Lemma 4* can be easily proven by contradiction)\n\nDirectly following *Lemma 4*, we get the following corollary:\n***Corollary 1*** After each time step, the value `max{machines}` decreases exactly by one (until reaches zero).\n\n***Lemma 5*** If `abs(D[i]) = max{abs(D)}`, let integer 0 <= `x` <= i, and integer i+1 <= `y` <= n-1, and `machines[x]` denote the nearest non-zero value to the lefthand of the demarcation line D[i] (i.e. `x` is the largest integer <= i s.t. `machines[x]` != 0), `machines[y]` denote the nearest non-zero value to the righthand of D[i] (i.e. `y` is the smallest integer >= i+1 s.t. `machines[y]` != 0), then `machines[x]` and `machines[y]` must be a combination of a positive and a negative (i.e. either `machines[x] > 0` and `machines[y] < 0`, or, `machines[x] < 0` and `machines[y] > 0`. Also, one could figure out that \'`machines[x] > 0` and `machines[y] < 0`\' corresponds to `D[i] > 0`; and that \'`machines[x] < 0` and `machines[y] > 0`\' corresponds to `D[i] < 0`).\n(*Lemma 5* is easy to prove by contradiction: assume `machines[x]` and `machines[y]` are both positive/negative...)\n\n*Lemma 5* basically says that the demarcation line with the largest absolute transfer value lies between a positive-valued machine (# dresses > `avg`) and a negative-valued machine (# dresses < `avg`). There might be some zero-valued machines lying in between, but we will see that it won\'t affect our analysis.\n\n\n**Now let\'s analyze any *i* s.t. `abs(D[i]) = max{abs(D)}`**. Without loss of generality, let\'s assume `machines[x] > 0` and `machines[y] < 0`, as the below picture demonstrates.\n

\nObviously, for any integer j s.t. x <= j <= y-1. D[x] = D[i] = D[y-1] = D[j].\nLet\'s divide the problem into different cases:\n**i.** L[x] <= 0. \nThat means `machines[x] <= abs(D[i]) = max(abs(D))`. In this case, we only care about D[i]. According to the earlier mentioned movement policy, after one time step `D[i]` will decrease by one, i.e. D_updated[i] = D[i] - 1.\n\n**ii.** L[x] > 0. \nThat means `machines[x] > abs(D[i]) = max(abs(D))`. In such case, we don\'t care about `D[i]` at all - whether it decreases or not does not affect the update for `M`.\n\nTogether with *Corollary 1*, we conclude that `M` will decrease by one for each time step (until it reaches zero) following our movement policy. And it is easy to recognize that if the current list `machines` is valid, the resulting updated `machines` list is also valid. Therefore, the minimum number of moves to balance all dresses is `M = max{max{abs(D)}, max{machines}}`.\n

Super Washing Machines

Problem Description

Problem Description

Answer Panel