Editorial for COCI '12 Contest 2 #3 Lanci


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Consider the situation where we have L chains and K open links. If L-1 \le K, we can use those K links to connect all the chains together (any two chains can be connected using a single link, so we need L-1 links to connect L chains).

If L-1 > K, 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 1, 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 1, 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

There are no comments at the moment.