RECRECOV - Editorial

PROBLEM LINK:

Practice
Contest

Author: Maksym Bevza
Tester: Istvan Nagy
Editorialist: Xellos

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Maximum flow.

PROBLEM:

You’re given a directed acyclic graph. Find the minimum number of disjoint paths in it which cover all vertices.

QUICK EXPLANATION:

The answer is N minus the maximum flow in a suitable graph. The maxflow can be found using Ford-Fulkerson.

EXPLANATION:

This is a fairly well-known problem - formally, we’re finding the size of a minimum path cover of our DAG. You can find a lot about it with a simple search query.

Motivation: let’s split each vertex v into 2 parts (let’s call them v_{in} and v_{out}) connected by an edge v_{in}\texttt{-> }v_{out} such that all edges directed into v will now be directed into v_{in} and all edges directed out of v will be directed out of v_{out}. Intuitively, a path is something like a flow of 1 in this graph and the splitting guarantees that no two “flows” can cross the edge v_{in}\texttt{-> }v_{out} for any v, which is something like path disjointness. And the solution really reduces to finding a maximum flow.

We’ll make a new flow-graph G_f in a similar way: there are vertices v_{in} and v_{out} in G_f corresponding to each vertex v in G and also edges u_{out}\texttt{-> }v_{in} in G_f corresponding to each edge u\texttt{ -> }v in G, but no edges v_{in}\texttt{-> }v_{out}. Instead, we’ll have a source s, a sink t and edges s\texttt{ -> }v_{out} and v_{in}\texttt{-> }t for each v. All edges have capacities 1.

The answer is N minus the maximum flow F in G_f between s and t. Why it works isn’t so obvious, unless we look at the problem from a different perspective - if there are P paths covering our DAG, they will have N-P edges in total (a path with v vertices has v-1 edges and there are N vertices in P paths), and we’re computing the maximum number of edges which can be assigned to paths. Those edges are the ones through which we’re sending the flow.

Think about what the constraints on edges of G_f mean: edges s\texttt{ -> }v_{out} with capacity 1 say that we can only send a flow of 1 through one outcoming edge (that actually appears in the DAG) from vertex v, edges v_{in}\texttt{-> }t mean a similar thing for incoming edges. Since any path cover corresponds to a valid flow and vice versa, the max. number of edges assigned to paths will be F and the minimum number of paths P=N-F.

We could also view it as bipartite matching of edges as outcoming to one vertex and incoming to another, where each vertex can only have at most 1 incoming and at most 1 outcoming edge. In fact, maximum bipartite matching can always be found as a maximum flow in a graph constructed by appending a source to one part and a sink to the other with unit capacities of all edges.

The graph G_f has O(N) vertices, O(N+M) edges and the maximum flow between s and t is at most N. Therefore, Ford-Fulkerson runs on it in O(N(N+M)) time and O(N^2) memory per test case without any trouble.

By the way, this problem is the exact topic of study of Dilworth’s theorem, which says that the minimum number of paths is the same as the length of the longest path in the complementary (undirected) graph of G. Feel free to read more about it.

AUTHOR’S AND TESTER’S SOLUTIONS:

The author’s solution can be found here.
The tester’s solution can be found here.
The editorialist’s solution can be found here.

RELATED PROBLEMS:

1 Like

Love it it was my problem right now. THank youI think you should try again and learn from your mistake… here you can join and find new experience in my blog Samsung J2 Spesifikasi, Smartphone Gahar Harga Murah http://ihluculucu.blogspot.com/2016/01/samsung-j2-spesifikasi-smartphone-gahar.html

To find the maximum flow in the newly formed bipartite graph, why can’t we use this approach:

c1 = Count the number of vertices having non-zero number of edges originating from it ,in the Vout list.

c2 = Count the number of vertices having non-zero number of edges converging into it ,in the Vin list.

The max flow would be the minimum of both these numbers,i.e., min(c1,c2).[Since any path needs one vertex from the outgoing vertices list, and other from incoming vertices list.]

I’m not able to find any case for which this approach fails.

Any help would be appreciated.

Consider the following situation:

  1. We have 4 pieces (N is 4): 1 2 3 4

  2. We have three edges (M is 3): (1, 2), (2, 3), (1, 3)

Clearly the 4-th piece is disconnected from the other pieces.

The description of the problem says the following:
"He wants to place all the pieces into lines such that any pair of consecutive pieces (L, R) in a line must be explicitly allowed by one of the M rules described above. In other words, for some i (1 ≤ i ≤ M), (Ai, Bi) = (L, R). "

So we can create the following line: 1 2 3. What about the 4-ths piece? We cannot add it to the mentioned line because none of the rules allows 4-th piece after the 3-rd one, so we have to insert the 4-th piece in a new line.

Is my reasoning correct?

can anyone explain this problem ??