Editorial for TLE '16 Contest 8 P5 - Prom Night
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.
Author:
The first two subtasks were intended to reward factorial/exponential time solutions.
First, we note that we do not need to consider females that the CS nerd is not interested in.
Next, in order to find the minimum number of females the CS nerd can choose from, we should pair up the females with the other males in a maximal way. We can accomplish this using a maximum bipartite matching algorithm. A max flow algorithm can be used, such as Dinic's or Edmonds-Karp, but the Ford Fulkerson method is easy to code and because of how the graph is structured, will run in time.
Time Complexity:
Comments