The Max-Flow approach: Note that this approach will be too slow for an actual implementation, but studying it can help us estalish some properties of the problem, which will be useful for the actual solution. In the Max-Flow realm, this is a standard supply and demand problem. We have a set of Engineers (supplies), where each can review some number of Components (each provides supply D(j)). On the other side, we have a set of Components (demands), each must be reviewed by some number of different Engineers (each requires C(i) demands). The graph will look like this: (1) There are two vertices, the source s and destination t. We will be measuring the s-t flow of the graph. (2) For each engineer (there are n = sum(b(j), j) <= 10^9 of them), create a vertex e. (3) For each component (there are m = sum(a(i), i) <= 10^9 of these), create a vertex c. (4) From each engineer e, create an edge (s, e) with capacity D(e), where D(e) is the number of components that engineer can review. (5) From each component c, create an edge (c, t), with capacity C(c), where C(c) is the number of reviewers required by that component. (6) For each possible pair of engineer e and component c, create an edge (e, c) with capacity 1. (7) All edges are directed. So, each engineer e has D(e) units of supply, and each component c has C(c) units of demand. The edges between the e-s and c-s have capacity 1, restricting that a component must be reviewed by different engineers (i.e., an engineer can only review a specific component once). The answer to the problem is Yes if and only if the maximum s-t flow of the graph is equal to sum(a(i) * C(i), i). That is, whenever the maximum flow uses up all the capacities of all out-going edges from all the components. This obviously is not feasible as an implementation, there are 2 * 10^9 vertices, over 2^18 edges, and the maximum flow can be as high as 10^14. ================================================================================ The Min-cut approach: Computing the maximum flow of the graph above is not feasible as an implementation. By applying the Max-flow-min-cut Theorem, we know that the maximum s-t flow always exactly equals the minimum s-t cut. Let's see how much easier it is to compute the min cut of the above graph. Note that the graph can be separated into 4 parts: the source {s}, the engineers {e-s}, the components {c-s}, and the destination {t}. Edges are all directed and go from one part to the next. So there are three kinds of edges: the ones going from s to the e-s, the ones going from the e-s to the c-s (all have capacity 1), and the ones going from the c-s to t. In a min s-t cut, edges are removed so that s is separated from t. Let S be the set of vertices that are still connected to s, and T = (V - S) be the set of vertices that are connected to t. We must have (s in S) and (t in T). Suppose we know S and T, how does the min cut look like? The min-cut will be the sum of capacities of all edges emitting from a vertex in S to a vertex in T, namely OPT = sum(capacity(x, y), x in S, y in T). OPT can be broken down into three parts based on the edge kind as described above: OPT = sum(capacity(s, e), e in T) + sum(capacity(e, c), e in S, c in T) + sum(capacity(c, t), c in S). But, capacity(e, c) = 1, so that simplifies to: OPT = sum(capacity(s, e), e in T) + sum(1, e in S, c in T) + sum (capacity(c, t), c in S). -- (Equation 1) Note that the second term only depends on how many of the e-s and c-s are in S. If there are p engineers in S and q components in S, then the second term is merely p * (m - q), where m = sum(a(i), i) is the total number of components. Further, note that the first and third term are independent of each other. The first term only cares about the engineers and the third term only cares about the components. Since OPT is the minimum cut, if we know p and q, we can select the (n - p) engineers with minimum capacity(s, e) to be in T and the q components with minimum capacity(c, t) to be in S. We have arrived at the point where, if we know p and q, the number of engineers and components to be included in S, then we can compute the min-cut just by selecting the correct engineers and components to be included in S based on the edge capacities (which is given in the input). It may seem like we haven't arrived at anything useful now, since there are still 10^18 (p, q) combinations where there can be 10^9 entities of each kind. Now we need to make use of the fact that the edges between and engineers and the components form a complete graph. Suppose we only know the value of p, can we find out the value of q? If p is known, which components should then be included in S? Lemma 1. Given p. (I) If capacity(c, t) < p, then c in S. (II) If capacity(c, t) > p, then c in T. (III) If capacity(c, t) = p, then c may be put in S or T without affecting OPT. Proof: Suppose we are give the min cut. (I) Assume there exists a component c with capacity(c, t) < p and c in T. Then, each e in S have an edge going into c with capacity(e, c) = 1 will contribute to OPT by 1 unit. Since the number of (e in S) is p, the contribution of these edges to OPT is exactly p units. If we change the min-cut by including c into S, then the value of this new cut is decreased by p units, and increased by capacity(c, t) units (incurred in the third term since now c in S). Since capacity(c, t) < p, capacity(c, t) - p < 0, so we have decreased the value of the min-cut, a contradiction. (II) Assume there exists a component c with capacity(c, t) > p and c in S. Then, if we move c into T, the value of the new cut is increased by p units (incurred in the second term) and decreased by capacity(c, t) units. Since capacity(c, t) > p, we have (p - capacity(c, t)) < 0, a contradiction. (III) Similar to the two arguments above, when capacity(c, t) = p, moving c into S (or T) would increase the value of the cut by p units, and then decrease it by p units. So, if capacity(c, t) = p, then c is free to be in either S or T without affecting the value of the min-cut. By Lemma 1, if we know p, then we know exactly which components to be included into S: all of the components with capacity(c, t) < p, and we may include any of the components with capacity(c, t) = p if we so choose to, but none of the components with capacity(c, t) > p. There are still 10^9 choices for p. But, note that since C(i) <= 10^5, capacity(c, t) <= 10^5 for all components c. This means when p > 10^5, we simply must include all components in S. Then, in Equation 1, the first term is always non-negative, the second term is zero, and the third term is sum(capacity(c, t), c). The minimum value of OPT when p > 10^5 can be obtained by simply also including all the engineers in S, making the first term zero, and so OPT = sum(capacity(c, t), c). That is to say, if p > 10^5, then OPT = sum(capacity(c, t), c). Thus, once p > 10^5, we have a single candidate for the value of OPT. For p <= 10^5, we may iterate through the values of p and compute the candidates of OPT by always inlcuding the p engineers with maximum capacity(s, e) and all components with capacity(c, t) <= p into S. ================================================================================ The Greedy approach: Note that the above approach can solve the proposed problem, but it does not provide an assignment of the engineers to the components. The max-flow approach can provide assignments for problem instances of smaller sizes. When an actual assignment is required, it can be computed using greedy algorithms, which we will outline below for the sake of studying this problem. These greedy algorithms are probably too slow for solving the proposed contest problem, but are interesting and can be used to produce an assignment when the problem instance is smaller. They are more efficient than the max-flow approach. Greedy approach 1: Iterate through the components in an arbitrary order. For each component c, assign the C(c) reviewers with maximum remaining quota to it, and reduce their quota accordingly. Greedy approach 2: Iterate through the reviewers in an arbitrary order. For each reviewer e, assign him/her to review the D(e) components with maximum remaining requirement, and reduce the requirements accordingly.