rafalk342's blog

How to prove this strategy?
By rafalk342, history, 9 years ago, In English

Recently a friend of mine gave me a problem to solve. You are given n numbers and initialize sum=0. You are doing steps until there is only one number left. In every step you take two numbers a and b, remove them from the set, add (a+b) to sum (sum+=a+b) and insert number (a+b) to our set. What is the smallest sum that you can achieve after this process?

Example: you are given numbers (1,2,3) and sum=0
1. You may take (1,2) then sum=3 or (2,3) then sum=5 or (1,3) then sum=4
2. Now you have numbers (3,3) or (5,1) or (4,2) and after this step sums are respectively sum=9 or sum=11 or sum=10
3. So the lowest sum you can achieve is 9

So I came up with a solution. In each step you take two smallest numbers. But I cannot prove that this strategy is correct. Are you able to prove or discard it?

  • Vote: I like it
  • -15
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
9 years ago, # |
← Rev. 4   Vote: I like it -27 Vote: I do not like it

Yes, I believe your logic might work! Although, the complexity of the solution might be little high after all find two minimum numbers and repeating the same process might require approx. (n square) operations!

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -22 Vote: I do not like it

    You can do it in O(n*logn), just keep those numbers in set structure. Then taking, erasing and inserting takes in each step O(logn).

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it -22 Vote: I do not like it

The proof is simple:

Assume n numbers in the array:

You can prove that 1 number will be added n times

1 number will be added n-1 times

and so on till

1 number will be added 1 time

So you have to minimise sum,where

sum = n*(a[x1]) + (n-1)*(a[x2]) + .... + 1*(a[xn])

Since we must minimise, obvious solution to sort the array and set xi = i and find sum

Hope it is clear

→ Reply
»
9 years ago, # |
  Vote: I like it -22 Vote: I do not like it

Yes, this is correct. This is a well-known technique actually: Huffman coding. You can find a proof in the article.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -22 Vote: I do not like it

    I don't see a proof there.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 3   Vote: I like it -19 Vote: I do not like it

      It seems that you're right, I also didn't find it there. But there's one on CLRS3, pages 433-434.

      The key idea is that each possible encoding corresponds to an arrangement of vertices in a (complete**) binary tree. It's not hard to notice that there exists an optimal encoding in which the two lower-valued nodes are siblings. You can combine these two nodes, inductively obtain an optimal encoding for the remaining ones and then un-combine them — this results in an optimal encoding for the original set of vertices.

      ** Technically the tree doesn't need to be complete, but this is always the case for an optimal encoding.

      → Reply
»
9 years ago, # |
  Vote: I like it -14 Vote: I do not like it

here is logic. however, we always do n — 1 operation. For each of operation we must take two min numbers and add sum of numbers has been token result, after that our result will be minimize...

→ Reply