Graph Theory, Hungarian Algorithm
There are two sets of N fighters. You are given the score earned by each team if a pair of fighters are matched. We wish to find the maximum difference of scores possible under the following constraints
- Once the pairing is done, any single fight may be cancelled all-together. This cancelled fight will try to reduce the score difference as much as possible.
- We wish to maximize the difference of scores. In case of tie, we want to choose the highest score.
The heart of the problem is the Weighted Bipartite Matching problem.
We can consider the following bipartite graph
- X is the set of fighters from home team.
- Y is the set of fighters from guest team.
- An edge between two fighters, one from home and one from guest, has weight equal to the score difference between the score that the home team gets and the score that the guest team gets for the fight between those two fighters.
We can calculate the maximum weight bipartite matching using the Hungarian Algorithm to know the maximum difference that the Chef can create. But, this ignores the possibility that the guest coach may delete an edge, after chef selects a matching.
The Guest Coach will obviously delete the edge with the maximum weight. Since, this will reduce the difference of the scores by the largest value.
But how do you calculate the weight of a matching as a function of the weight of the highest weighted edge? Since, this function is not metric, we cannot do anything trivial (such as ignore the weight of the highest weighted edge for a matching).
We can however, sort all the edges and consider them incrementally by adding them to the graph one by one.
This looks like it would force the recalculation of the weighted matching. But we cannot run the procedure Hungarian-Matching after adding every single edge. This would give us an O(n5) which is too slow.
Refer to this pdf for how addition of a single edge may not invalidate the entire matching. We can handle the case of edge addition by simply invalidating the matching between the pair of vertices and adjusting the α and β arrays for the row and column respectively.
In doing so, we only need to adjust the matching once. This adjustment is part of the Hungarian Matching algorithm and occurs in O(N2) time.
If the new edge is part of the weighted matching, then we must ignore the weight of this edge iff the weight is positive. Since, the Guest coach will not cancel the match in case the match with the maximum weight already benefits the guest team!
By considering the edges in this way, we can calculate the maximum score difference the home team can achieve in O(n4) time.
The last little detail to consider is how to handle the tie-breaking. This part is not trivial too
Please refer to the first comment by anton_lunyov for a beautiful explanation on handling it.
The original (and wrong) approach posted in the editorial was as follows:
In case there are multiple ways to achieve the maximum differece, we know that we must select the one with the maximum score to the home team. To handle this we can consider each edge’s weight as
pair (score difference, score to home team)
Now, the maximum weight selected will always select the maximum score difference first, and in case of ties, consider the case that gives the home team a higher score!
Can be found here.
Can be found here.