DNA Chopper

Problem G - DNA Chopper

Ok, getting past the added flavourtext, what it turns out you have to do is this:
Given a list of n numbers, continuously remove two numbers from the list and put their sum back into the list, and add the sum to your total cost - stopping once you only have one number in the list. Find the minimum cost of doing this.

[Unfortunately?] It just so happens that this is a well-known and solved problem, helping in the area of compression (to see how, I'd recommend reading about Huffman Coding). It also so happens that it's used in numerous contests (e.g. TopCoder problem 'DiskCut' and various other ACM contests) so anyone who's done many matches is likely to have seen this.

The algorithm for solving it is pretty much the greedy approach to that mentioned above - in the 'remove two numbers step', you simply remove the two lowest numbers. This can be done quickly, and in very little code, using a priority queue (set up to remove the lowest number in the queue) - code that implements this can be read here, and is a reminder that even hard ACM questions can often be solved in very little code, even without obfuscation.

It seems this was not the most common way to solve the problem however, and judging by the input bounds of 15 numbers, it seems it was not the inteded solution either - I'd be interested to know if the problem writer knew of this approach.
Anyway, with 15 numbers, another method is to perform a DP solution, where your state is a bitmask with a 1 for numbers you can use, and a 0 for those you can't. cost(mask) is then the sum of the numbers you can use, plus the minimum value of cost(submask) + cost(mask - submask), where submask is a subset of the values you can use - e.g. submask | mask == mask.

If you memoize the values for each mask, you get a complexity of about O(2^15 states * time-per-state) where time-per-state is between 2^14 and 1, but on average small, and apparently with optimisations this passes (just) under the timelimit - although much slower compared to the O(n log n) queue solution.