You are not logged in. Please login at www.codechef.com to post your questions!

×

LEMPLOY - Editorial

PROBLEM LINK:

Practice

Contest

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:

  1. Among all pairs of nodes i,j within the same layer, an edge of capacity D[i][j] from j to i.
  2. Edge from source to all nodes of layer 1, with capacity INF.
  3. Edge from all nodes in layer M to sink , with capacity MAX-P[i][m].
  4. Edge from all nodes in layer (j-1) to corresponding nodes in layer j with capacity P[i][j-1] for 2<=j<=M
  5. 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[i][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[i]. We claim N*MAX - (cut of above graph) is the value of total productivity of the firm if person i is given role R[i] for all i.

Reason:

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

AUTHOR'S SOLUTION:

Author's solution can be found here.

asked 03 Oct '16, 22:11

gvaibhav21's gravatar image

7★gvaibhav21
947210
accept rate: 25%

edited 03 Oct '16, 22:21

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,719
×1,343
×1,228
×114
×26

question asked: 03 Oct '16, 22:11

question was seen: 948 times

last updated: 03 Oct '16, 22:21