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 
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 
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
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 
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 
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
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
1 Like
Yeah, give the whole solution, thatās the spirit 
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
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?