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