### PROBLEM LINK:

**Author:** Vaibhav Gosain

**Editorialist:** Vaibhav Gosain

### DIFFICULTY:

HARD

### PREREQUISITES:

maxflow, min cut: Topcoder Tutorial

### EXPLANATION:

This problem can be solved via the concept of minimum cut.

We model the following graph, containing M+2 layers:

0th and (M+1)th layer for source and sink, M other layers for each role in firm, each containing N nodes.

Edges:

- Among all pairs of nodes i,j within the same layer, an edge of capacity D*[j] from j to i.
- Edge from source to all nodes of layer 1, with capacity INF.
- Edge from all nodes in layer M to sink , with capacity MAX-P*[m].
- Edge from all nodes in layer (j-1) to corresponding nodes in layer j with capacity P*[j-1] for 2<=j<=M
- Edge from all nodes in layer j to corresponding nodes in layer (j-1) with capacity INF for 2<=j<=M

where MAX = maximum possible value of P*[j]

The required maximum productivity of the firm = N*MAX - mincut

**Why does this work?**

Let S be the source and T be the sink.

The infinite edge from layer j to layer j-1 ensures that if ith node in layer j is on the S side in the cut, corresponding node in layer j-1 will also be on the S side in the cut.

Now, say the last layer whose ith node lies in S side of the cut is R*. We claim N*MAX - (cut of above graph) is the value of total productivity of the firm if person i is given role R* for all i.

Reason:

- Productivity contributed by P*[R*] is due to the edge between layer R* and layer R*+1.
- For any 2 people i and j such that R[j] > R*, there will be R[j]-R* layers for which node j is on S side of cut and node i is on the T side. Hence the value D*[j] will be added R[j]-R* times to the mincut.

### AUTHORâ€™S SOLUTION:

Authorâ€™s solution can be found here.