Stuck at add-em up

Puzzles
#1

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:

#2

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
#3

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

#4

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
#5

Thanks a lot! I think I understand now!

#6

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:

#7

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
#8

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
#9

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

2 Likes
#10

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)
#11

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.

#12

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
#13

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

1 Like
#14

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

#16

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:

#17

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?