Noam527's blog

By Noam527, history, 6 years ago,

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.

• +51

| Write comment?
 » 4 years ago, # |   +8 Have you found a solution since then?
 » 4 years ago, # | ← Rev. 2 →   0 somewhat similar problem?
•  » » 4 years ago, # ^ |   0 In this question you can only combine adjacent slimes, whereas in the question he posted, you can combine any two elements you want.
 » 2 years ago, # | ← Rev. 2 →   -26 You can solve it in O(n^3) :)