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:
3 5 (+8)
2 3 (+5)
I played around with it, but then I found this case:
1 4 5 7 9 10
The greedy solution will yield:
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:
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,
(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
There’s a simple proof here.