PROBLEM LINK:Author: Gaoyuan Chen DIFFICULTY:HARD PREREQUISITES:Maxflow, Graphs PROBLEM:You are given N courses and M semesters. X[i][j] is the expected grade which you will get for completing the ith course in jth semester or 1 if ith is not taught in jth semester. You are also given K prerequisites. Each one is in form (i, j) and means that course i has to be taken before course j. Your task is to compute the maximum possible expected average grade if you have to take every course exactly once. QUICK EXPLANATION:Model the problem and prerequisites as mincut / maxflow problem and find a maxflow in it corresponding to the maximum achievable expected sum of grades. EXPLANATION:First, let's ignore the dependencies. The answer is just the maximum grade per course in any of the semesters, which is trivial to compute but let's put this in another perspective:
To model this as a network flow graph, we do 4 things:
Consider the following example with 3 courses and 3 semesters:
The corresponding graph is depicted in the above picture. The maximum flow is equal to the combined grade loss for all courses. We pick semester 3 for course 1 (zero loss), and semester 1 for courses 2 and 3 (loss 20+20). The maximum grade average we can get is (N * 100  maxflow) / N. In this case: (3*100  40) / 3 ~= 86.67.  Returning to the problem, why does this help? If we model the problem this way, we can also include the course dependencies. Suppose there are dependencies 1>2 and 1>3. The best we can do is course 1 in semester 2 and courses 2 and 3 in semester 3 for (70+40+40)/3 average.  If there are dependencies 1>2 and 1>3, then courses 2 and 3 can never be done in the first semester. This implies that the minimum grade loss for courses 2 and 3 is not bounded by its grades in semester 1. This is the same as changing the capacities associated to semester 1 of courses 2 and 3 to infinity.  Why do we pick semester j for course 1? The combined grade loss of doing course 1 in semester 2 + courses 2 and 3 in semester 3 is less than doing course 1 in semester 1 + courses 2 and 3 in semesters 2 or 3. In terms of network flow, this means that
The resulting network is the following We can see that the maximum flow is 150. The best is to distribute the grade loss of course 1 in semester 2, flow 3, among courses 2 and 3 in semester 3. In fact, 70+40+40 = 300  150. To give you another example, consider the input
The best we can do course 1 at semester 1 (10) + course 2 at semester 2 (90) and course 3 at semester 3 (70) = 10+90+70. The resulting graph is We can see that the maximum flow is 130 because in this case, it is better to distribute the grade loss of course 1 at semester 1, the flow 90, among the grade loss of courses 2 and 3 over semesters 2 and 3, respectively. In a nutshell, we create a graph with N*M+2 vertices and use a standard maximum flow algorithm. The hard part was to realize how to build the network correctly. Proof sketch: Since maxflow equals mincut, we can think of our problem as of finding a minimum cut in the above graph. Let P_{i} be a path corresponding to ith course, i.e. the path formed of edges corresponding to ith course in all semesters. In order to prove the correction of the above construction, we can show two properties of the graph:
These two fact can be shown quite easily, but we will omit exact proofs here. Intuitively, if you pick any edge from P_{i}, then P_{i} is disconnected and there is no need for taking any other edge from it. Moreover, an edge (i, j) corresponding to a constraint, prevent us of taking course j before course i, because if you did it, then in order to make the graph disconnected, you would have to add the second edge of P_{j} to mincut which contradicts the first fact. AUTHOR'S AND TESTER'S SOLUTIONS:To be uploaded soon. RELATED PROBLEMS:To be uploaded soon.
This question is marked "community wiki".
asked 29 Dec '14, 23:27

Shouldnt we add some positive constant to all weights of edges because otherwise we can get a mincut which does not satisfy 1st fact of proof. If not,can someone sketch the proof of 1st fact ?? answered 05 Feb '18, 18:52

well, better late than never ;)
I'm not sure, this is "official" editorial  http://discuss.codechef.com/questions/58386/pleaseexplaintherinsnetworkflowsolution/59078 @mogers good job anyways ;) If I'm correct I'd remove "community wiki" mark
My original post was just my explanation without any intention of being an editorial.
Today there was a chat with the CodeChef team and it was improved by @pkacprzak to this version as the official editorial.
Thanks, for explanation ;)