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.
        Submitting an official solution before solving the problem yourself is a bannable offence.
Let  be the number of animals with a preferred job category of 
. We can tally up the values of 
 and 
 in 
 time by iterating over each of the 
 animals and adding onto the correct counts. The maximum number of animals who prefer job category 
 and can be assigned to it is then 
. Similarly, the maximum number of animals who prefer job category 
 and can be assigned to it is 
. 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 
.
Comments