Editorial for DMPG '19 B6 - Oddity


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.

Author: r3mark

Let s_i be the number of stamp types that friend i has and let t be the number of stamp types that Alice has. Observe that Alice satisfies the constraints if and only if s_i + t is odd for all i. So the only important feature of a collection for this problem is the parity of the number of stamp types. Then Alice should either take the cheapest stamp type, or the cheapest two stamp types, or it is impossible. Checking which of these possibilities works can be easily done by checking the parity of each s_i.

Time Complexity: \mathcal{O}(NK)


Comments

There are no comments at the moment.