A transversal week

The TopCoder Open onsite continued during the Oct 23 - Oct 29 week with Semifinal 2 on Monday (problems, results on the left, our commentary). Two contestants got the medium problem this time, tourist and ikatanic, and bcip was the third advancer thanks to fast time on the easy. Congratulations to all advancers!

The final round of the TopCoder Open took place just 24 hours later (problems, results on the left, our commentary). One again just two contestants have managed to solve two problems, and xudyh was quite a lot faster than rng_58. Congratulations on the TopCoder Open victory!

Codeforces Round 443 took place on Thursday (problems, results, top 5 on the left, analysis). dotorya has dominated the proceedings, solving all problems in the end, but having enough points for a clear first place with just four of them. Amazing performance!

On the weekend, the Open Cup Eastern Grand Prix took place (problems, results, top 5 on the left). Five teams have solved all problems, and team Past Glory did it faster than everybody else. Well done!

In my previous summary, I have mentioned a Codeforces problem: you are given a bipartite graph with at most 200000 vertices each each part. Each vertex in the left part has exactly two edges to different vertices in the right part. Each vertex in the left part also has a weight. You need to find the weight of the maximum weight matching in this graph (but you don't need to output the matching itself).

First of all, we can find the maximum weight matching greedily, by trying to add the vertices in the left part in decreasing order of weight, since the set of left parts of matchings forms the transversal matroid. How do we check if a vertex in the left part can be added to the matching without building the traditional augmenting path, which would be too slow in this problem? Since we don't need to build the matching itself, we will rely on the Hall's theorem. Suppose we're adding a vertex a in the left part that is connected to vertices b and c in the right part. Consider the connected components of the graph formed by the right part plus the vertices in the left part which have been matched (whenever we can't match a vertex in the left part, we disregard it together with the adjacent edges). Each of those components has at least as many vertices in the right part as in the left part, since all vertices of the left part are matched. Moreover, if it has k vertices in the left part, then it has 2k edges, and since it also has at least k vertices in the right part, its total number of vertices is at least 2k. A connected graph with at least 2k vertices and 2k edges does not have that many possibilities: it either has exactly 2k vertices and has one cycle, or it has 2k+1 vertices and is a tree.

We claim that we can add the vertex a to the matching if and only if one of the components corresponding to b and c is such a tree, so all we need to maintain in our solution is a set of connected components using a disjoint set union data structure, and the number of vertices in each part for each connected component.

If both components corresponding to b and c are not trees, they have the same number of vertices in left and right parts, and the union of those components and vertex a has more vertices in the left part than in the right part, so the Hall's theorem tells us it's impossible to add a to the matching. If the component corresponding to say, b, is a tree, then let's prove it's possible to rearrange the matching inside this component in such a way that we can add a to the matching. Suppose it's impossible, then the Hall's theorem tells us that there exists a subset U of vertices of the left part of the component such that if V is the set of the right part vertices adjacent to U,  then the size of V is equal to the size of U.  If U has k vertices, then the graph formed by U and V has 2k vertices and 2k edges, which means that it has a cycle, which is a contradiction.

Thanks for reading, and check back for more!