PROBLEM LINK:
Author: Harsh Sahu
Editorialist: Harsh Sahu
DIFFICULTY:
Medium-Hard
PREREQUISITES: Max-Flow
PROBLEM:
Given N bowlers and performance measure of each of the bowler a quadratic function with input from Li to Ri. We need to maximize the sum of performance of each of the bowler with certain type of constraints. Here O(u) is the number of overs bowled by uth bowler. Then according to problem there is a restriction on number of overs bowled by vth bowler i.e. O(u)<=O(v)+d.
Hence the problem reduces to maximize function g=∑fi(Oi) for i from 1 to n with given m constraints on various Oi .
QUICK EXPLANATION:
Here I describe how this function to be maximized can be converted to max-flow problem. First of all for each variable Oi we create (Ri -Li +2) node labelled as V(i,Li-1),V(i,Li)…to V(i,Ri).Also we create a source vertex and sink vertex. Then we assign weights to link source to each V(i, li - 1) with capacity of infinity and also link each V(i, ri) to sink with capacity of infinity.Finally we link each V(i, x - 1) to V(i, x) with capacity of MAX - fi(x). Here MAX is a number greater than every possible value of the variables.Now consider the restrictions. Suppose a restriction is O(u)<=O(v)+d, then for each V(u, x), link it to V(v, x - d) (if exists) with a capacity of infinity. Let C denote min-cut/ max-flow of the constructed graph. So if there exist a solution then n*MAX-C will be the maximum performance.
DETAILED EXPLANATION:
You must be wondering why we did the above stuff and how can this guarantee the optimum performance. First let us assume that there are no restriction then the min cut of the graph must contain the edge with weight MAX- fi(x) where it is minimized for x∈{li,li+1,li+2…ri} and hence for each i function fi(x) is maximized. So the answer will be nMAX- C. Now consider that there is restriction of the type O(u)<=O(v)+d, then for each V(u, x),we had linked it to V(v, x - d) (if exists) with a capacity of infinity. The observation to be made here is that if the above constraint is not followed then min cut of the graph will contain edge from V(u,Ou) to V(v,Ov) with weight infinity. Hence if the ans to max-flow/min-cut is greater than or equal to infinity then it is impossible to satisfy the constraints. Else the answer will clearly be nMAX-C.