Proof of CSES Stick Divisions?

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
1 Like

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

1 Like

There’s a simple proof here.

2 Likes