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