[Community Puzzle] Add'em Up

Coding Games and Programming Challenges to Code Better

Send your feedback or ask for help here!

I tried to solve this problem: Coding Games and Programming Challenges to Code Better

What I came up: Find and delete two minimum integers. Insert sum of found integers. Repeat it until the size of the list become 1.

I think this greedy algorithm works. However, I’m not sure how to (mathematically) prove this algorithm.

Any suggestions? Thanks.

The number oft additions is constant for a given set of integers.
So I would try induction…?

1 Like

The evaluation of the sum can be represented by a full (each internal node has two children) binary tree whose leaves are the numbers of the initial list (Xi)i and the internal nodes represent the operations. Let Di be the depth of the leaf Xi in the evaluation tree. It is not hard to see that the cost of the evaluation is Sumi XiDi.

Let us prove that there exists a minimal-cost tree in which the two (or two of the) smallest values leaves are children of the same node (at the maximum depth). Indeed, consider a minimal-cost tree and any deepest internal node, its two children must be leaves, say of values a and b and of depth D maximum in the tree. Consider any other leaf c, say of depth Dc ≤ D. Swapping a (or b, whatever) and c in the tree generates a cost difference of a(Dc-D) + c(D-Dc) = (c-a)(D-Dc). But if c ≤ a, then (c-a)(D-Dc) ≤ 0 and this implies (c-a)(D-Dc) = 0 (otherwise we would have found a tree of a lesser cost). Consequently if a and b are not yet the two smallest values, we can swap these values with a and b while keeping the cost minimal, hence building an optimal tree satisfying the property.

This proves that an optimal strategy can always start by adding the two smallest values: This gives you the greedy choice strategy to follow. Pick the two smallest values, replace them by their sum and repeat on the new set of values.

NB: For a complete formal proof, look for Huffman Coding on the internet: replacing the frequencies/probabilities of the letters by the input numbers should lead to the same problem.

2 Likes

Hi everyone

While I have mastered almost all easy-puzzles without trouble, I am completely stuck at this one:

They given example just doesn’t tell me how this cost thing works, if there are multiple numbers. Well at first I thought I would understand:
numbers: 1,2,3
1+2= 3
3+3= 6
Total cost: 9 (correct)

numbers: 1,3,4,4
1+3= 4
4+4= 8
8+4= 12
Total cost: 24 (correct)

numbers: 9,9,9,9,9,9,9,9,9 (9x9)
9+9= 18
18+9= 27

72+9= 81
Total cost: 396 (WRONG - correct answer: 261)

The only way I get to 261 is, when I do the following:
9+9= 18
18+9+9= 36
36+9+9= 54
54+9+9= 72
72+9= 81
Total cost: 261
But this algorithm doesn’t work with the first two examples. I cannot find an algorithm that works for all of the 3 examples.

Can anyone help me to understand this puzzle? I have already spent at least 5 hours trying to understand what is wanted… I would really appreciate if someone could bring some sense into this :smiley:

You must find the lowest cost, which you can’t get by simply adding numbers in sequence.
For example :
9+9+9+9 :
sum first 9s : 9+9 = 18 → your numbers are 18,9,9
9+9 = 18
18+18 = 36

1 Like

Thank you for trying to help me!

But sadly I am still confused. Maybe I don’t understand what is ment by “cost”…

Would you show me how to get the total cost of the following numbers:
1,3,5,7,9

You can only add two numbers. Not a+b+c, only a+b, then (a+b)+c.
so you can also try b+c, then (b+c)+a
each time you add two numbers, the result of that addition is “the cost”

in your example: 1,3,5,7,9

1+3 = 4 (cost->4)
5+7 = 12 (cost->12)
4+9 = 13 (cost->13)
13+12 = 25 (cost->25)
total costs: 54

try different orders of addition, and see how the total costs differ

HTH

2 Likes

Thanks a lot! I think I understand now!

I still don’t get it :frowning:

why ist the last digit 9 added to cost 4? and why are the costs 12+13 added for an additional cost, but 4+12 is not?

maybe I need a bigger sequence to understand… 1,3,5,7,9,11,13
1+3 = 4 (cost 4)
5+7 = 12 (cost 12)
9+11 = 20 (cost 20)
?+13 = ? (cost ?)

I feel so stupid :smiley:

ignore the costs for a moment.
you need to add up all numbers to get the total sum.
since you can only ever add up two numbers at the same time, you have to use the intermediate sums as new numbers…
a short array:
1 2 3 4 5
add up 1 and 2, sum: 3. now 1 and 2 are used, and 3 is your new summand.
new array after step one:
3 3 4 5
add up 3 and 3, sum: 6. now 3 and 3 are used, and 6 is your new summand.
new array after step two:
6 4 5
add up 6 and 4, sum: 10. now 6 and 4 are used, and 10 is your new summand.
new array after step three:
10 5
last step: 10+5

each step uses one addition. which has a cost you need to add up.

headscratch does that make it clearer? i’m not the best at explaining stuff :slight_smile:

it can be drawn as a binary tree (up side down):

1 2 3 4 . 5 6 7 8
. 3 . 7 … 11 .15
… 10 … … 26
… … . 36

but that will not give you the optimum :wink:

2 Likes

OMG, i think finally got it! I am allowed to add up any 2 numbers at every “round”, am I correct?

1 2 3 4 5 → 1+2 (cost 3)
3 3 4 5 → 3+3 (cost 6)
6 4 5 → 4+5 (cost 9)
6 10 → 6+10 (cost 16)
total cost 34

1 Like

Passed all testcases. I can’t believe how easy programing the solution was once I understood what to do :smiley:

2 Likes

Could you please, explain the solution? Why do you sum up first and second items, but in ‘6 4 5’ set you sum up second and third one?

Can someone give me the algorithm to solve “9 9 9 9 9 9 9 9 9” data set?

9 9 9 9 9 9 9 9 9 (cost = 0)
.18 18 18 18    9 (cost = 72)
...36    36     9 (cost = 144)
......72        9 (cost = 216)
...........81   9 (cost = 297)

Just think of “rounds”. And in every round you are allowed to sum up any two numbers in the set.

round 1:
1 - 10 - 4 - 3
(1+3) - 10 - 4
creating a new set
4 - 10 - 4

round 2:
4 - 10 - 4
(4+4) - 10
creating a new set
8 - 10

do this until you have 1 number left. then sum up all the additions.

One important thing - every round we have to sum up not any but two minimal numbers!

Here is the iterations during Task3 solving:

9.9.9.9.9.9.9.9.9
.18.9.9.9.9.9.9.9 | 18
.18..18.9.9.9.9.9 | 18
.18..18..18.9.9.9 | 18
.18..18..18.18..9 | 18
.18..18..18...27. | 27
...36....18...27. | 36
...36.......45... | 45
........81....... | 81
...........TOTAL: | 261
2 Likes

Well I didn’t want to spoil it too much :smiley:

1 Like

Yeah, give the whole solution, that’s the spirit :laughing:

Ok I was comparing all the combinations and my algotythm worked but got timeout on long calculations.
Adding always the lowest values was the key.

Thnks for the tip :slight_smile:

I can’t have 100% to the test. I followed the algothme describe above. Every “round” sum the two minimum card. Any idea why it doesn’t pass all the tests?