lbm364dl's blog

Minimum cost of merging array numbers
By lbm364dl, 2 years ago, In English

This problem is from here (in Spanish). You can submit there. Here I leave a simplified statement.

You have an array $$$a$$$ of $$$n$$$ numbers ($$$n \le 20$$$) with values $$$a_i \le 20$$$. The value of a merged set of numbers is the sum of the numbers. You are asked to find the maximum possible value of a number, after merging numbers with a total cost of at most $$$m$$$, $$$m \le 500$$$. The cost of merging two numbers is the sum of the cost of each number. Initially, the cost of each number is its value.

Note that this is not the same as this problem, which has a greedy solution related to Huffman encoding (there the cost of a merge is just the sum of values).
The reason of the title is that I guess I should just find the minimum cost of merging each subset of numbers and then find the maximum value among those with a cost not exceeding $$$m$$$.
Also, in the original problem $$$n \le 15$$$, but I write $$$20$$$ here because my $$$O(3^n)$$$ bruteforce iterating subsets of subsets gets time limit because of too many test cases.
I guess the solution has something to do with bitmask DP. I was not familiar with this technique so I searched some problems but I can't relate them to this one. Any help is welcome.

EDIT: I misunderstood the statement and this is actually the same as Huffman (the other problem I claimed was not the same as this one). I apologize.

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You probably want to read about sum over subsets DP.

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

    Thanks. I have read this (this is where I learned about the $$$O(3^n)$$$ brute force), and I'm sorry if I'm missing something, but I don't see how I could apply the DP optimization explained after that. I have trouble with the base case. We should say my problem is about 'minimum over subsets'. In the sum over subsets problem, you just add the sum of the whole subset as a base case. What should I do for my problem? The minimum over the whole subset is what I actually want to compute. I'm confused.

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

      Oh, sorry I just read that you want a DP over subsets. I think the problem doesn’t actually need it though. I think you can solve in $$$O(n2^n)$$$.

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

        I said that because I had no other ideas so I thought it was something about DP, but I just want to solve it. Does your complexity involve a brute force? Would you mind giving some hints at least? If it is something obvious I don't really see it. Thank you.

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

          Sorry, can you explain again why the cost function is different from Huffman?

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

            I apologize for making you lose your time. The cost function was actually just Huffman, and I got accepted now. I misunderstood the statement. It says that the cost of merging is the sum of costs, so I understood I had to use the total cost I needed to obtain each of the numbers previously, rather than just 'the cost of merging is the sum of values'. To clarify what I thought the cost was, see this example:
            Merge 1 2 3 4 from left to right.
            What I thought:
            (1+2) + ((1+2)+3) + ((1+2)+(1+2+3)+4) = 22
            Actually just Huffman:
            (1+2) + (3+3) + (6+4) = 19

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

There should be an appropriate analogue of the Huffman encoding greedy algorithm for this cost function. Then, I expect it's enough to just apply that greedy strategy $$$2^n$$$ times.

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

Can't you just iterate over each subset and do huffman on those cards only and see if cost is in bounds? Or am I missing some detail?

→ Reply