PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
Let G[t] be the bipartite graph at time t with boys on one side and girls on the other where only the boys and girls who are present at time t occur. There is an edge in G[t] between each couple who is willing to dance with each other at time t. Let M[t] denote the size of the maximum matching in G[t]. Say t’ is the next event where a person either enters or exits. I claim that |M[t’] - M[t]| <= 1. If a person entered then assume, for the sake of contradiction, that M[t’] >= M[t] + 2. Then all but at most one edge in this matching in G[t’] involves this new person and after possibly removing such an edge we get a matching of size greater than M[t] in G[t]. If a person exited then at most one matching is destroyed.
So, given a maximum matching in G[t] we can get a maximum matching in G[t’] in the following way. If a person entered at t’, then simply see if there is an alternating path in G[t’] with respect to the matching in G[t]. If so, then the matching increased and if not then the matching size is the same. If a person left at t’, then discard the matched edge they were involved in (if any) from the maximum matching and then see if there is an alternating in path in G[t’] with respect to this modified matching. In fact, if the person was not matched when they left then we don’t have to bother with finding an alternating path.
Overall, we initialize the graph to be empty and sort the events where a person enters or exits in increasing order of time. Then we process these events one after the other and look for a single alternating path each time. For each interval between events, we add the length of this interval to the time spent with the corresponding maximum matching size. The number of events is O(B+G) and the time it takes to update the matching is linear in the size of the graph, which is O(BG) in the worst case but much better on intervals when few people are dancing. The overall running time is O((B+G)BG).
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.