Hi, someone asked me to upload an editorial with my approach to CHEFDAG because it apparently seemed easier than the video tutorial. Here it is:

Observations:

- It is suboptimal for the in-degree of any node to be >1
- The resultant graph is based upon a topological sort so it will definitely be acyclic, we don’t have to specifically check
- If we restrict the in-degree and out-degree of all nodes to <= 1, the problem breaks down to finding the maximum number of edges we can create in the graph.

N <= 500 so intended solution is O(N^3)

The first part of the solution is to make an adjacency list with all valid edges. This is fairly straightforward in O(N^3) so I’m not going to go into it. If someone specifically wants to know then leave a comment.

Now we have an acyclic graph where the out-degree of certain nodes might be >1. We need to keep only a subset of these edges so that the out-degrees are <=1.

My solution to this part is as follows:

Divide **each node** into 2 parts, let’s call them A and B. A and B are sets of nodes (both with size N). Now, if there was an edge directed from node u to node v, create an edge between node u in set A and node v in set B.

Note that we now have a bi-partite graph. According to observation 3, we have to maximise the number of edges in this graph. This is a simple **maximum bi-partite matching** problem. The algorithm runs in O(N^3) so it should pass comfortably.

You can learn the algorithm here:

My (somewhat unreadable) solution:

https://www.codechef.com/viewsolution/30076944