Editorial for COCI '12 Contest 2 #3 Lanci
Submitting an official solution before solving the problem yourself is a bannable offence.
Consider the situation where we have chains and open links. If , we can use those links to connect all the chains together (any two chains can be connected using a single link, so we need links to connect chains).
If , we do not have a sufficient number of open links, so we need to open more. If we open a link in the middle of a chain longer than three links, we will increase the number of chains by , which is obviously not optimal. Therefore, it is always best to remove links from either end of the chain. Furthermore, if a chain consists of a single link, opening it reduces the number of chains by , which leads to a better solution. We conclude that it is best to take new links from either end of the currently shortest available chain, until we have enough open links (since the shortest chain will be the first to be completely taken apart and thus reduce the chain count).
Comments