Borisp's blog

By Borisp, 13 years ago, In English
This is translation of author's solution of Div 1 problem E of round 80.
Italics are Borisp's notes.

This problem's statement and Russian solution is by winger.

Construct bipartite graph G1 with available sets on the left side and the numbers on the right side. We put an edge from a set to all the numbers contained in it. By Hall's theorem it follows from "the union of any k sets contains no less than k distinct numbers (for every positive integer k)" that there exists perfect matching of all the elements in the bipartite graph (in fact the theorem states that there exists matching including all set vertices, but as the numbers are also restricted by n, this means that there exists perfect matching).

After this observation we find whichever perfect matching in G1, let's denote it by M = {(ui, vi)}. Now we construct second oriented graph G2 with vertices corresponding to the available sets and edges (ui → uj) for each edge (ui, vj) from G1 that do not occur in M (Note that the matching sets the indices of v's and thus we consider them, not the values of the corresponding numbers). Now for every suitable collection of size k there should be no outgoing edge to other set in G2 (otherwise the numbers included in the sets of the collection will be k plus the additional few numbers from the corresponding outgoing edges and the collection will not be suitable - more numbers than sets).

Thus our problem has been transformed to the following equivalent: in an oriented graph with weight of vertices find subset S of the vertices with minimum sum of weights and without outgoing edge with other end not in S. This problem is known to be equivalent to finding minimum cut (I wasn't able to prove the equivalence, didn't know it by heart either, but I found it even easier to prove if I consider the task as just max flow) .

Assign to the edges of G2 infinite weights, add additional vertices s and t,. Now for every set ui with weight w add edge ui → t with weight w iff w > 0 and edge s → ui with weight  - w iff w < 0. The part of the minimum cut of s and t in the constructed graph that contains s is the sought optimal collection (in fact what I did was sum the outgoing weights from s after computing max flow in the graph; I was able to prove this is the required number).

  • Vote: I like it
  • 0
  • Vote: I do not like it

12 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I've been trying to understand how to solve this problem but for the first example:

n = 3
m1 = 1: 1
m2 = 2: 2 3
m3 =1: 3

The max flow part doesn't seem to work. The network would be: an edge from s to 3 with capacity 3, an edge from 1 to t with capacity 10, an edge from 2 to t with capacity 20, and an edge from 2 to 3 with infinite capacity. And the max flow is zero.
  • 12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Well I think I now understand that when you said "in fact what I did was sum the outgoing weights from s after computing max flow in the graph; I was able to prove this is the required number" you meant that you substract this from the result you obtained of the max flow, that seems to work, but could someone explain me why?