Rigorous proof of the correct strategy and the O(1) formula solution
After reading several posts in this discussion, I wasn\'t able\xA0to find a formal rigorous\xA0proof of why the O(n) sorting (or priority queue) method works or
After reading several posts in this discussion, I wasn\'t able\xA0to find a formal rigorous\xA0proof of why the O(n) sorting (or priority queue) method works or why the O(1) formula\xA0method is correct. So, after some thought, here is a proof.\nI don\'t think it should\xA0be considered an "easy" problem even though the actual solution is simple.\n\n### Problem statement\n\nI use a slightly\xA0different formulation of the problem since it is more convenient.\nWe have 3 columns of non-negative integer\xA0height. Our goal is to reach a state where all of them are zero with two types of operations:\n1. Decrement 1 from one of the columns.\n2. Decrement 1 from two\xA0different\xA0columns.\n\nThe task is to calculate the minimum number of steps necessary.\n\n### Lower bound\nAs others already mentioned, there are two obvious\xA0lower bounds:\n1. max(columns): since at each step a maximum\xA0of 1 is decremented from a single column.\n2. ceil(sum(columns) / 2): since at each step a maximum of 2 is decremented from the sum of the\xA0columns.\n\nSo the lower bound is the maximum of the two numbers above.\n\n### Proof the lower bound is also reachable\nLet\'s denote the column values a >= b >= c >= 0.\n\n(1) If a >= b+c, then we use c steps to remove c from the first and last columns and reach a-c, b, 0. Then, we use b steps to remove b from the first and second to reach a-b-c, 0 ,0. Then, we remove the remaining with a-b-c steps. We used a total of exactly c\xA0+ b\xA0+ a - b - c = a = max(columns) steps, thus achieving our lower bound.\n\n(2) Now suppose that, a < b+c.\nLet x = a-b >= 0 and y=b-c >= 0. Therefore, we have: a=x+y+c, b=y+c. At first, we use y operations (from the second type) to decrement y from the two largest columns. After that we have the values x+c, c, c where x < c.\n\n(2.1) If x+c is even:\nThere exists k>0 such that x+c=2k. Note that k < c since x < c. We use k steps to remove k from the first and second columns to reach k, c-k, c. Now again use k steps to remove k from the first and third columns to reach 0, c-k, c-k. Finally, use c-k steps to zeroize the two equal remaining columns. All the steps we used were from the second type, i.e. remove 2 each time so the total number of steps was exactly sum(columns) / 2 and we again reached the lower bound.\n\n(2.2) If x+c is odd:\nThere exists k>0 such that x+c=2k+1. Note that k < c since x < c. We use k steps to remove k from the first and second columns to reach k+1, c-k, c. Now again use k steps to remove k from the first and third columns to reach 1, c-k, c-k. Finally, use c-k steps to zeroize the two equal columns and one more step of the first type to zeroize the first column. All the steps except the last one were from the second type so the total number of steps was exactly\xA0ceil(sum(columns) / 2)\xA0and we again reached the lower bound.\n\nQ.E.D\n\nPlease note the above also proves the correctness of the sorting (or priority queue) strategy.
['Math']