Does anyone know how to (formally) prove the greedy solution to CSES Stick Divisions?

I am not sure. The best greedy algorithm I can think of is taking splitting a sum using the maximum available number. For example, the sample test case would be split into:

8

3 5 (+8)

2 3 (+5)

I played around with it, but then I found this case:

36 6

1 4 5 7 9 10

The greedy solution will yield:

36

10 26 (+36)

9 17 (+26)

7 10 (+17)

5 5 (+10)

1 4 (+5)

For a total of 94.

However, while experimenting I found this solution based on my intuition of splitting into nearest-possible halves:

36

18 18 (+36)

9 9 10 8 (+18+18 = +36)

4 5 7 1 (+9+8 = +17)

For a total of 89.

I do not know if this will always work. For instance in the case of 8=2+3+3,

I get

8

4 4

(No solution)

(3,5) would be the closest pair for the second step, but I donâ€™t know how to definitively tell what a step should be. In the above experimentation, I put (18,18), where 18 is not already one of the desired numbers.

If you can guide me to the greedy approach, that would be great. I am not sure how to prove it, though. Thanks!

Hereâ€™s my approach (untested)â€¦

## Solution to CSES Stick Divisions

- â€śReverseâ€ť the process: add small sticks to form one big stick
- Put all the desired stick lengths into a multiset
- Greedily take the two smallest sticks, then merge them, then put the resulting stick back into the multiset
- Repeat until thereâ€™s only one stick left

That should be correct. This problem is essentially equivalent to Huffman encoding (https://en.wikipedia.org/wiki/Huffman_coding#Basic_technique) which I think you could figure out if you look at the similarity between what you do and what the Huffman algorithm doesâ€¦

So technically I donâ€™t know the formal proof but I know that the proof of Huffman encoding would be it