Noam527's blog

Help: Minimize merge operations
By Noam527, history, 7 years ago, In English

I came up (I think, I just didn't see it anywhere) with this problem earlier today and I think it's better if I ask for help here as I still don't know its solution:

You have an array of N integers and in each step you can merge any 2 of them into a single integer (and then this integer is added to the array while the previous 2 are erased from it). The cost of merging two elements X and Y is max(X, Y).

You need to find the minimal cost you can get after merging all the integers into 1 (essentially, doing N — 1 merges).

Currently there's no constraint (not on N, nor on the limit of the integers) so just try to come up with the best complexity you can.

Examples:

input:
3
4 6 8
output:
16

(merging 4 and 6 to 10 with the cost of 6, and then merging 8 and 10 with the cost of 10, giving a total of 16).

input:
4
10 11 13 16
output:
55
(10->16) + (11->13) + (24->26) = 16 + 13 + 26 = 55.
  • Vote: I like it
  • +51
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Have you found a solution since then?

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

somewhat similar problem?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In this question you can only combine adjacent slimes, whereas in the question he posted, you can combine any two elements you want.

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

You can solve it in O(n^3) :)

→ Reply