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

×

MAXPER editorial

PROBLEM LINK:

Practice Contest

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.

asked 16 Mar '16, 15:53

harsh23's gravatar image

2★harsh23
211
accept rate: 0%

edited 22 Mar '16, 17:00

admin's gravatar image

0★admin ♦♦
19.0k348495533


Your Editorial is Wrong on constraints!

link

answered 11 Jul, 23:25

userhacker's gravatar image

4★userhacker
101
accept rate: 0%

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:

×14,441
×1,094
×102
×21
×5
×1

question asked: 16 Mar '16, 15:53

question was seen: 593 times

last updated: 11 Jul, 23:25