Editorial for WC '16 Contest 4 J1 - Anyone Can Be Anything


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.

Let C_i be the number of animals with a preferred job category of i. We can tally up the values of C_1 and C_2 in \mathcal O(N) time by iterating over each of the N animals and adding onto the correct counts. The maximum number of animals who prefer job category 1 and can be assigned to it is then \min(O_1, C_1). Similarly, the maximum number of animals who prefer job category 2 and can be assigned to it is \min(O_2, C_2). Note that these two quantities don't conflict with one another, and that any remaining animals who can't be assigned to their preferred job category can simply be assigned to the other one, without worrying about taking away any other animal's preferred spot. As such, the answer is \min(O_1, C_1)+\min(O_2, C_2).


Comments

There are no comments at the moment.