Kiraru's blog

By Kiraru, 7 weeks ago, In English

This is a problem that came to me by chance and I don't know how to solve it

  1. Given n positive integers

  2. Choose any two integers a and b and merge them into a+b, the cost of the operation is max(a,b)

  3. Repeat the operation until there is only one number left, find the minimum possible cost

I found a similar problem on the web, and in that one, the cost of the operation is a+b.

In that problem, the solution is to choose the smallest two integers in every operation.

Unfortunately, it can't work in this problem.

For example

1 2 2 3

If we always choose the smallest two integers

the process will be 1 2 2 3 -> 2 3 3 -> 3 5 -> 8 and the cost is 2+3+5=10

However,if we do like this: 1 2 2 3 -> 2 2 4 -> 4 4 -> 8, the cost will be 3+2+4=9

 
 
 
 
  • Vote: I like it
  • +41
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Can you give a link to the problem?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry, no link. Because the problem is set by myself and I don't know whether there is already the same problem on the web.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

You should go for a Greedy method:

sort the array, always operate on A[i] and A[i+1] such that A[i+1]-A[i] is smallest.

I have not proven it neither found a counter-example but I hope you may found this helpful!

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    sorry, but I seems to find a hack.

    array: 2 5 10 11

    greedy process: 2 5 10 11 -> 2 5 21-> 7 21 ->28, and the cost is 11+5+21=37

    but there is a better way: 2 5 10 11-> 7 10 11-> 11 17 ->28, and the cost is 5+10+17=32

    upd: well, even the sample given in the statement (1 2 2 3) can hack this method

»
7 weeks ago, # |
  Vote: I like it -18 Vote: I do not like it

It sounds like a dp, cause greedy solutions doesnt work

»
7 weeks ago, # |
Rev. 2   Vote: I like it -29 Vote: I do not like it

Q

»
7 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

How about we take an approach based on, instead of constructing the total from the bottom, we partition the final number into two and recurse? For example, we start from the total sum — $$$8$$$ in your example, can be represented in multiple ways, 4+4and 3 more. I think we may be able to construct a DP solution, but I am not yet fully able to implement one.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    UPDATE: I think I came up with the states for DP, It could be done by $$$DP[N]=min_{m=ceil(N/2)}^{N} {DP[N-m]+DP[m]+m}$$$. However I think, in this case, keeping the array's state would be very hard.

»
7 weeks ago, # |
Rev. 3   Vote: I like it -18 Vote: I do not like it

In a sorted array, if $$$\sum_{i = 1}^{n - 1}{a_{i}} \le a_{n}$$$, just proceed from left to right. Also, if $$$a_{n - 1}$$$ makes the $$$\sum_{i = 1}^{n - 1}{a_{i}} > a_{n}$$$, assuming that no $$$\sum_{i = 1}^{k}{a_{i}} \ge a_{n}$$$, $$$k < n - 1$$$ then also proceed from left to right.

So I guess the other case would be to minimize the maximum value attainable which I don't know.

»
7 weeks ago, # |
  Vote: I like it +24 Vote: I do not like it

Can you guys think before commenting? Every comment is "well maybe it works if we always take the two cutest numbers" with no analysis, proof or even vague intuition.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think mine isn't :thinking:

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    How could we solve this problem? Could you kindly provide some hints or ideas leading to the solution?

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I have no good ideas. I don't think there is a reason to expect that it can be solved in polynomial time.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

no