This Is Really An Addition Problem

Computer Science Level 5

Define the cost of adding two numbers together as its sum. For example, adding $1 + 2$ has cost 3. When we want to add two numbers, the cost is easy to compute, but when we want to add more numbers, there are various ways to do the additions, by choosing which two numbers to add next. While all of them will give the same sum, not all of them will give the same total cost.

For example, suppose we want to add the numbers 1, 2, 3, and 4. There are various ways to do this. As examples:

Add 1 and 2 together (getting 3), then add our 3 with the original 3 (getting 6), then add our 6 with the 4 (getting 10). This is represented as $(((1+2)+3)+4)$ , and its cost is $3 + 6 + 10 = 19$ .
Add 3 and 4 together (getting 7), then add our 7 with the 2 (getting 9), then add our 9 with the 1 (getting 10). This is represented as $(((3+4)+2)+1)$ , and its cost is $7 + 9 + 10 = 26$ .
Add 1 and 2 together (getting 3). Add the original 3 and the 4 together (getting 7). Add our 3 and our 7 (getting 10). This is represented as $((1+2)+(3+4))$ , and its cost is $3 + 7 + 10 = 20$ .

There are 18 ways to add those four numbers. Out of all of them, the minimum cost is achieved when we add $(((1+2)+3)+4)$ , with cost 19.

There are approximately $1.374 \times 10^{284}$ ways to add 100 numbers. What is the minimum total cost of adding these 100 numbers ?

The answer is 22047074.

1 solution

Agnishom Chattopadhyay
Jul 13, 2016

Relevant wiki: Heaps

A way to visualize this problem is to see it as a list of $n$ numbers being transformed to a list of $n-1$ numbers at each step. That is, we are taking away two numbers and adding back their sum.

1	`[1,2,3] -> [1,5] -> [6]`

Now, at each step, the cost is the sum of the two numbers we'll add. It is also the number that goes back into the list.

In order to minimize the total cost, we'll follow a greedy strategy. At each step, we'll add the two least numbers. (This should be intuitively obvious now, but if someone can prove this, it'd be helpful.)

So, how do we efficiently get the two least number at each step? Sorting each time works, but luckily there is a more efficient solution. Heaps .

import urllib2, heapq

#Get the data
heap = map(int,urllib2.urlopen("http://pastebin.com/raw/0LuGxwCM").read().split())

# Build the heap - linear time
heapq.heapify(heap)

cost = 0
while len(heap) != 1:
  x = heapq.heappop(heap) #get the smallest element - logarithmic time
  y = heapq.heappop(heap) #get the smallest element again - logarithmic time
  cost += (x + y)
  heapq.heappush(heap,(x+y)) #add back the new value - logarithmic time

print cost

So, that get's the job done in $O(n \log n)$ time.

Let me try giving the greedy proof since I had a hard time convincing myself to "just code it!".

What makes us to not choose the two minimum number each time? Easy, because we might get an even smaller number afterwards (think of why we don't always take the maximum denomination in the coin change problem). But is it possible? If I do not sum up the two minimum number (which equal to x), in later summations none will add a cost smaller than x. Hence we can just greedy.

Christopher Boo - 4 years, 11 months ago

The previous version of this problem is wrong; there aren't $\binom{100}{2} \cdot 98!$ ways to add 100 numbers together, there are $\binom{100}{2} \cdot \binom{99}{2} \cdot \ldots \cdot \binom{2}{2}$ ways. Because the first one was the one presented, I initially thought you had to add the previous sum with one of the numbers; that is, I thought $((1+2)+(3+4))$ was not allowed (because it adds 1 and 2 together, then puts it off and adds 3 and 4 together first).

Ivan Koswara - 4 years, 11 months ago

I think Pi Han has reverted the edits. Does the problem look acceptable now?

Agnishom Chattopadhyay - 4 years, 11 months ago

When I read the problem, it was the first version I stated; I then edited it to show the second version, the current one. I'm not sure if there was a previous version before.

Ivan Koswara - 4 years, 11 months ago

This Is Really An Addition Problem

The answer is 22047074.

1 solution

0 pending reports