MARTARTS - Editorial

[gamabunta]

PROBLEM LINK

Practice
Contest

DIFFICULTY

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(n⁵) 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(N²) 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(n⁴) 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.

[anton_lunyov]

It seems that tie-breaking part in the editorial is incorrect. It coincides with my first try to solve the problem which appears to be absolutely wrong. In fact, in the case of tie, guest Chef will delete the minimum edge since his second goal is also to maximize his total score. So if for example all score differences are equal and positive for each game then we have the opposite problem: we should maximize SUM - MIN where SUM is the sum of edges in our matching and MIN is the minimum edge.

The described incremental approach should be seriously modified to become correct. Consider this test:
2
6:5 1:0
10:9 6:5
(I have found test like this by stressing my old solution with naive one)

We see that all differences are equal to 1. If we consider edges one by one in any natural order (from minimal to maximal or vice versa) and try simply add them and recalculate the matching we always choose matching (6:5, 6:5) which leads to the answer 6:5 for the home Chef. Of course the correct answer is 10:9.

What should we do to handle this?

At first let’s sort edges by another comparator: edges with lower score difference should come first as before but edges with equal score difference should come in decreasing order of score. Then when we consider some edge we assume that this edge is exactly the edge thrown away by the guest Chef (if its score difference is <=0 then we shouldn’t consider it from this point of view). This means that we should include it to the matching by force (it appears to be the main change to the previous solution) and all other edges in the current graph should be worse for guest Chef than considered one. This is achieved exactly by our modified comparator. To include the edge by force we simply set scores for other edges of this two vertexes to -INF and then recalculate the matching in O(N * N) as described in the editorial (it is easy to see that this forced include destroys two edges of the old matching and creates one new edge so we should recover just one edge as before). We use natural comparator from editorial for dealing with matching. The new comparator is needed only for sorting edges. The matching thus obtained is the optimal matching for the fixed edge that guest Chef will throw away, so we update the answer by it.

After that we add the edge to the initial matching before this include, as in solution described in editorial, and proceed to the next edge.

BTW, I enjoyed the problem very much because of this tricky tie-breaking part. Applause to the author!

P.S. Russian speaking contestants can read also this part of the awesome article on e-maxx.ru about Hungarian algorithm to learn how to make rebuilding part in O(N * N) time. Shame on me, but I simply copy-paste the code from there. However some modifications were needed, so probably it would be simpler to write it from scratch.

[thocevar]

I’m glad you enjoyed the problem. The tie-breaking part is not trivial and you described it very nicely. Home and guest coach have opposite goals when optimizing the score difference. But they have the same goal of increasing the total score for breaking ties.

Too bad that it’s only in Russian. The solution seems much more compact than the other popular source which deals with implementation details of O(n^3) Hungarian algorithm - http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm

[bcurcio]

I used this approach but couldn’t get in time limit. But I know where my problem is, I just don’t understand how you are dealing it.

My problem is when there are many ties. For each edge I need to try to force it in the matching. If I do this, I’m not able to use the algorithm that works in O(N^2), because I’m removing 2N edges! and adding some more. So every time I have ties I need to rerun O(N^3).
How are you able to force the matching AND being able to adjust in O(N^2)?

[thocevar]

I don’t see why do you change O(n) edges. You don’t have to add or remove any edges, just change their weight from -INF to add them. Let’s say you want to force a match between nodes X and Y. Set their edge weight to INF and unmatch their current matches if they have them. You can update the node potentials and rerun at most two iterations of Hungarian algorithm.

[bcurcio]

One option is doing that, but the other is setting to -INF the cost of all adjacent edges to the nodes you are trying to match (I think that’s the one anton explained). I didn’t use setting an edge to INF because I thought it would break the cover in some way for the next iteration, but I think it makes sense now, I’ll try it.

[anton_lunyov]

Hm… Changing edge to INF sounds much simpler.

In my solution when we set many edges to -INF (in fact I use -10*INF where -INF is used for not yet added edges) we need to change just two values of potential and as I explained delete two edges from the matching and add one edge so using O(N^2) is possible.

[anton_lunyov]

Also the workflow for the INF (or -INF) version should be like this. Let (G,P,M) be the graph, potentials and the matching from the previous step. Copy (G,P,M) to (G’,P’,M’) change the copied triple, recalculate the matching and update the answer. Then add new edge to the original graph (G,P,M) as in the editorial.

[mugurelionut]

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.