Codeforces Round #290 (Div. 1 C / Div. 2 E) - Fox and Dinner

Problem Statement:
512C - Fox and Dinner

Solution:
I've always been fascinated with maximum flow problems. The author to this problem is brilliant, and his official editorial is very well written, succinct and sweet. This post is mostly for my future reference, but feel free to read through the discussion :)

We can certainly identify that this problem is a matching problem, but what exactly is the type of matching we are interested in? On the first glance it seems to require some notion of tables, in which each table must contain at least 3 elements. That sounds like a random constraint, but as it turns out, a pretty fundamental observation to this problem can leads to a very clever representation of the problem that can easily enforce the constraints described in the problem statement.

Codeforcees Round 283 Div. 2 Problem E - Distributing Parts

Problem Statement:
496E - Distributing Parts

Solution:
This is more for self-reference, I suggest you read the official tutorial on Codeforces for a better discussion on this problem.

This problem is a bipartite matching problem: match smaller "job" segments into bigger container "worker" segments, where each worker segment has certain capacity. If we model each segments as vertices, then we have a graph with \(V\) vertices. This problem cannot be solved efficiently using maxflow algorithm, since V can be very huge, hence there must be some greedy idea behind it. And as I learnt from the editorial, the idea is to consider both jobs and workers in increasing order of their lower bounds. In this iteration, we keep track of a set S of workers that we have encountered, which has the following invariant:
For all i, by the time we reach i-th segment, the lower-bound of this segment is always bigger or equal to any lower bounds of segments in S.

Hence if the i-th segment we are facing is currently a job segment, we just need to find a worker segment in S that has a bigger upper bound than that of the job segment. If there are multiple choices, we must choose the lowest one available. I think this choice can be proven to yield optimal matching by exchange arguments.

If the implementation of S is done by using RB tree, the running time of this algorithm will be \(O(V\lg{V})\).

TopCoder SRM 640 Div.1 550 - MaximumBipartiteMatchingProblem

Problem Statement:
SRM 640 Div.1 550 - MaximumBipartiteMatchingProblem

Solution:
A very mathematical problem I guess, we will get to optimise a quadratic function. Firstly, take ans vertices from both n1 and n2, and match them like this:

ans pairs of vertices:

o o o o o  -> upper-end
| | | | |
o o o o o  -> lower-end

That means we have (n1-ans) unmatched vertices from the first set F, and (n2-ans) unmatched vertices from the second set S. We cannot match any of these unmatched vertices amongst themselves, because it will immediately increase the number of bipartite matching. So we can only match them with those ans paired vertices