×

HARD

# PREREQUISITES

Graph Theory, Hungarian Algorithm

# PROBLEM

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.

# QUICK EXPLANATION

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).

# EXPLANATION

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!

# SETTERS SOLUTION

Can be found here.

# TESTERS SOLUTION

Can be found here.

This question is marked "community wiki".

2.4k128183169
accept rate: 14%

 4 For educational purposes, I should mention that a maximum cost - maximum flow algorithm can also be used successfully instead of the Hungarian algorithm (but only by adding multiple optimizations). In essence, my solution is the same: I consider the edges in reverse order of the preference of removing them: i.e. edges with larger difference first and for edges with equal difference, edges with lower sum first; then, for each edge, I force it into the matching and try to compute the optimal matching considering only edges which are less preferred than it (i.e. edges with lower difference or with equal difference and >= sum). As mentioned in the editorial and in anton_lunyov's post, we do not need to recompute the optimal matching from scratch each time, but rather only update it. Nevertheless, max cost - max flow algorithms are an order of magnitude slower than the Hungarian algorithm. So what optimizations can be used ? 1) I used the Bellman-Ford-Moore (BFM) shortest path (in this case "longest" path with two criteria - difference and sum) algorithm -- this is in theory O(N^3), but it always runs much faster than that : it uses a simple queue in which a node is inserted whenever the optimal distance to it is updated 2) I also used the "parent checking" heuristic for BFM - i.e. when you extract a node from the queue, don't do anything with it if its parent is already in the queue again (this can be extended to multiple levels - e.g. the parent's parent, etc.) 3) Instead of BFM, it is well known that Dijkstra's algorithm can be used on a graph with modified edge costs -- I implemented this, but my implementation was slower than BFM (both with priority queues and the standard O(N^2) version) 4) There is no need to update the flow on only one path at a time - just like in the case of Hopcroft-Karp's maximum matching algorithm, we can update the flow on multiple vertex-disjoint paths after running the shortest path algorithm -- this reduces the number of times the shortest path algorithm is run, which is in fact the bottleneck in this solution. 5) Finally, after running the shortest path algorithm: 5.1) count how many nodes on the right side of the bipartite graph are reachable: if any unmatched node is unreachable then stop, as you won't be able to find a perfect matching 5.2) sum up the optimal costs of reaching each unmatched node on the right side of the bipartite graph and then add this sum to the current cost of the matching ; if, after the addition, you do not get a value larger than the best one found so far, then stop (as the optimal matching in this case will be worse than the best one found so far) -- note that in this case you do not consider the cost of the forced edge (which will be the one removed by the opponent team) Of course, the other case left is when the opponent team does not remove any edge from the matching - in this case a simple optimal matching on the graph containing only edges with difference <= 0 will suffice. answered 14 Nov '12, 18:00 10.0k●26●69●90 accept rate: 18%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,482
×1,329
×97
×86
×17

question asked: 12 Nov '12, 22:49

question was seen: 6,604 times

last updated: 14 Nov '12, 18:00