C++ 16ms O(n) solution (with trivial proof)


  • 56
    M

    First we check the sum of dresses in all machines. if that number cannot be divided by count of machines, there is no solution.

    Otherwise, we can always transfer a dress from one machine to another, one at a time until every machines reach the same number, so there must be a solution. In this way, the total actions is sum of operations on every machine.

    Since we can operate several machines at the same time, the minium number of moves is the maximum number of necessary operations on every machine.

    For a single machine, necessary operations is to transfer dresses from one side to another until sum of both sides and itself reaches the average number. We can calculate (required dresses) - (contained dresses) of each side as L and R:

    L > 0 && R > 0: both sides lacks dresses, and we can only export one dress from current machines at a time, so result is abs(L) + abs(R)
    L < 0 && R < 0: both sides contains too many dresses, and we can import dresses from both sides at the same time, so result is max(abs(L), abs(R))
    L < 0 && R > 0 or L >0 && R < 0: the side with a larger absolute value will import/export its extra dresses from/to current machine or other side, so result is max(abs(L), abs(R))

    For example, [1, 0, 5], average is 2
    for 1, L = 0 * 2 - 0 = 0, R = 2 * 2 - 5= -1, result = 1
    for 0, L = 1 * 2 - 1= 1, R = 1 * 2 - 5 = -3, result = 3
    for 5, L = 2 * 2 - 1= 3, R = 0 * 2 - 0= 0, result = 3
    so minium moves is 3

    class Solution {
    public:
        int findMinMoves(vector<int>& machines) {
            int len = machines.size();
            vector<int> sum(len + 1, 0);
            for (int i = 0; i < len; ++i)
                sum[i + 1] = sum[i] + machines[i];
    
            if (sum[len] % len) return -1;
    
            int avg = sum[len] / len;
            int res = 0;
            for (int i = 0; i < len; ++i)
            {
                int l = i * avg - sum[i];
                int r = (len - i - 1) * avg - (sum[len] - sum[i] - machines[i]);
    
                if (l > 0 && r > 0)
                    res = std::max(res, std::abs(l) + std::abs(r));
                else
                    res = std::max(res, std::max(std::abs(l), std::abs(r)));
            }
            return res;
        }
    };
    

  • 1
    Z

    Thanks for your detailed explanation, it's very helpful!


  • 7
    L

    @Mrsuyi said in C++ 16ms O(n) solution:

    Since we can operate several machines at the same time, the minium number of moves is the maximum number of necessary operations on every machine.

    Though this statement is indeed true, we need a formal proof for that.


  • 0

    Thanks for your elegant solution and detailed explanation!


  • 0
    J

    Really elegant solution and nice explaination.


  • 5
    M

    @lixx2100
    I think I have got a proof, but it's not very precise.
    My solution contains two step, the first step is to calculate the "Necessary" actions on every machine, and the second step is to choose the max actions as the result. Our worry lies in the second step, because there may exist a situation where a machine has some action to do, but it cannot be done at some time. For example:
    [4, 0, 0, 0]
    The last machine needs to import a dress from left side, but in the first 2 rounds of action it cannot be done, because the left machine is empty.

    Now, let's think in another way. In every moving-strategy, each dress has its fateful moving-path. Each dress has to be transferred from one machine to another until it reaches its destiny, so we can mark that path by drawing a S===>D line, S for source and D for destiny. For example:

    [4, 0, 0, 0]
     S=>D
     S====>D
     S=======>D
    

    Three dresses has to be transferred from machines[0] to others. Because a machine can only do one action in a round, moving path cannot overlap with each other except their destiny is the same machine(a machine can import 2 dress from both side at the same time), like S===>D<===S, but we can just merge them with S=========S, it won't affect the final result. Actually, we don't even care about S and D, we only care about how many machines a path covers.

    So what is "Necessary" actions of a machine? It is the value of overlapping paths below the machine in the graph. For example:

    [1,  0,  5]
     D<======S
         D<==S
         D<==S
    

    In this case, we have 3 moving-paths, and they overlap on the last machine, so we have to arrange them in 3 rounds. We can see that "Necessary" actions is [1, 3, 3] from the graph.
    But there exists a lot of arranging strategies, we can just insert an empty round that no machine does anything, so the total rounds is 4.
    What we need to prove is that, if a "Best Strategy" with round M exists, there must exist one machine which is covered by M paths. And that means in the graph, there is no "Hole (not covered by any path)" under machines which occupies all M rounds. If this is true, then the max "Necessary" actions is M, and total rounds is M. For example:

    [A,  B,  C,  D]
     <====
         ====>
             =====>
    

    or we can do

    [A,  B,  C,  D]
    <=====   ====>
         ====>
    

    Notice that in the first strategy, there is 1 hole under C in first round, 2 holes, under D in first and second round, the max "Necessary" actions is 2 but it requires 3 rounds. There is no hole in second strategy, both "Necessary" actions and rounds are 2.

    Now, if we can find an algorithm to get the "Best strategy" which contains no "Hole", the problem is solved. Here comes the algorithm.

    1. Sort all moving-paths according to their start-point in ascending order;
    2. Start round 1
    3. Choose the path available (not overlapping with chosen ones in this round) with smallest start-point into this round. Keep doing this until no available path exist
    4. If there are paths left not chosen, start a new round and go to step 3

    In the example of [A, B, C, D], there are 3 paths [A, B] [B, C] [C, D]
    so the algorithm works like this

    [A,  B,  C,  D]
    <====
    then
    [A,  B,  C,  D]
    <====    ====>
    then
    [A,  B,  C,  D]
    <====    ====>
         ====>
    

    Assume that we get a solution for arranging paths in M rounds, consider the first path in the last round. The machine, covered by that path's start-point, will never have a "Hole". I mean, something like this won't appear:

    <===  Hole
      <=======
    <========
           <=====
    

    Because in this situation, the path on last round should have been chosen in first round. So, If there is M round in given solution, there must exists a machine covered by M paths. Therefore, the "Necessary" actions is M, and we got a solution to execute all these actions in M rounds, problem solved :D

    I came out with this algorithm inspired by Interval Scheduling problem
    https://en.wikipedia.org/wiki/Interval_scheduling

    And I came out with my solution for this problem inspired by this problem
    http://poj.org/problem?id=1083

    I think this proof is totally a mess, and I wish someone can bring a clearer and easier proof :D


  • 18
    L

    @Mrsuyi I have also come up with a proof. Let me know what do you think. :)

    For each machine-i, we use L[i] to denote the number of dress it needs to pass to its left neighbor. And L[i] = 0 if machine-i does not need to transfer any dress to its left. Symmetrically, we define R[i].
    To compute these quantities, we break the array into two parts, say a[1 .. i] and a[i + 1 .. n] and it is easy to compute R[i] and L[i + 1], respectively.

    Now, define f[i] = L[i] + R[i], and let M = max(f[i]). We then claim that M is our answer. Clearly, M is a lower bound of this problem as every machine can only send one dress at a time. It then suffices to show that M is feasible by constructing a sequence of moves such that every machine will eventually contain an equal number of dresses. Below is the construction algorithm, where we don't care about its runtime but only its correctness.

    while(M > 0) {
        for (i = 1 to n)
            if (f[i] < M) Do nothing.
            else {
                if (R[i] > 0) Machine-i passes a dress to its right.
                else Machine-i passes a dress to its left.
            }
        Recompute M based on the current configuration.
    }
    

    To see the correctness, it is clear that M will decrease by one after each iteration because all those bottleneck machines release a dress simultaneously. (This is because if R[i] > 0 then it is impossible to have L[i + 1] > 0, and vice versa.) Therefore, after M iterations M would become zero, which implicitly means that the workload in every machine is even.

    Finally, we still need to prove that at any time, every bottleneck machine has something in hand to pass by. The formal proof is given in the following lemma, and we are eventually done.

    Lemma: If f[i] == M, then a[i] must be positive, i.e., the i-th machine has at least one dress to pass.
    Proof.
    For a contradiction, assume a[i] == 0 instead.

    We first show it is impossible to have L[i] > 0 && R[i] > 0. The reason behind that is simple: R[i] > 0 means the total dresses in a[i + 1 .. n] is insufficient; similarly, L[i] > 0 means a[1 .. i - 1] is lack of dresses. But since a[i] == 0 there is no way to fulfill these requirements. --- A contradiction.

    Now, without loss of generality let L[i] == 0 && R[i] > 0. We then show R[i - 1] > R[i] and, as such, f[i - 1] = L[i - 1] + R[i - 1] >= R[i - 1] > R[i] + 0 = f[i], which contradicts to the fact that f[i] == M.
    We left the question "why R[i - 1] > R[i]?" to the reader as a good exercise.


  • 0
    M

    @lixx2100
    excellent idea and precise proof

    So because R[i] > 0 every machine requires at least 1 dress, therefore R[i - 1] = R[i] + [dress-to-i] > R[i], am I right?


  • 1
    L

    @lixx2100 I believe the reason "R[I - 1] > R[I]" is we assume "a[I] == 0", so in fact, R[I - 1] = R[I] + avg in this case. As avg is a positive value, R[I - 1] is obviously larger than R[i]


  • 0
    S

    said in C++ 16ms O(n) solution (with trivial proof):

    For example, [1, 0, 5], average is 2
    for 1, L = 0 - 0 * 2 = 0, R = 5 - 2 * 2 = 1, result = 1
    for 0, L = 1 - 1 * 2 = -1, R = 5 - 1 * 2 = 3, result = 3
    for 5, L = 1 - 2 * 2 = -3, R = 0 - 0 * 2 = 0, result = 3
    so minium moves is 3

    Shouldn't L and R be calculated the other way? I mean should't it be as follows:
    For example, [1, 0, 5], average is 2
    for 1, L = 0 * 2 - 0 = 0, R = 2 * 2 - 5= -1, result = 1
    for 0, L = 1 * 2 - 1= 1, R = 1 * 2 - 5 = -3, result = 3
    for 5, L = 2 * 2 - 1= 3, R = 0 * 2 - 0= 0, result = 3
    so minium moves is 3


  • 0
    M

    @snrao18
    Ah yes you are right, my mistake.
    I have fixed that. Thanks!


  • 0
    S

    @Mrsuyi Elegant solution and nice explanation!


  • 0
    Y

    @Mrsuyi Great!


  • 0
    T

    @lixx2100 A+++++


  • 0
    Y

    @Mrsuyi
    Thank you for the solution. But still not get the idea. Can you elaborate the solution on this example:
    [1,2,2,2,2,3]


  • 0
    L

    @Mrsuyi Yes! :)


  • 0
    L

    @lakecarrot Yes! :)


  • 0
    M

    @ylc0sky
    for 1, the left side requires 0 dress, and right side requires -1 dress, so total moves is max(abs(0), abs(-1)) = 1 (get 1 dress from right side)
    for all 2, left side requires 1 dress and right side requires -1 dress, total moves max(abs(1), abs(-1)) = 1 (pass 1 dress from right side to left)
    for 3, left = 1, right = 0, max(abs(1), abs(0)) = 1 (export 1 dress to left side)

    so max moves is 1


  • 1
    C

    Thanks for the brilliant solution!

    Java version:

    public class Solution {
        public int findMinMoves(int[] machines) {
            int n=machines.length, sum[]=new int[n+1];
            for (int i=1;i<=n;i++) sum[i]=sum[i-1]+machines[i-1];
            if (sum[n]%n!=0) return -1;
            int need=sum[n]/n, ans=0;
            for (int i=0;i<n;i++) {
                int l=i*need-sum[i], r=(n-1-i)*need-(sum[n]-sum[i+1]);
                ans=Math.max(ans, l>0&&r>0?l+r:Math.max(Math.abs(l), Math.abs(r)));
            }
            return ans;
        }
    }
    

  • 0
    Y

    @Mrsuyi Thanks for the prompt reply. It helps. But would you illustrate more about how you get this solution, after all it is not very typical. I mean what is the thinking model that leads to such a solution. where did you start that inspired you to get this solution.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.