PROBLEM LINK:
Author: Shiplu Hawlader
Tester: Mahbubul Hasan and Sunny Aggarwal
Editorialist: Balajiganapathi Senthilnathan
Russian Translator: Sergey Kulik
Mandarian Translator: Minako Kojima
DIFFICULTY:
Hard
PREREQUISITES:
Linear Programming, Dual of Mincost Max Flow
PROBLEM:
Given M integers L_{xy} (1 \le x \le N and 1 \le y \le N) we want to find N integers P_x (1 \le x \le N) and N integers Q_y (1 \le y \le N) such that for each of the M given integers, W_{xy} = L_{xy} + P_x - Q_y is within the range (S_{xy}, T_{xy}) inclusive. If there are several solutions possible, output the one with the least sum of all W_{xy}.
EXPLANATION:
Thanks to the author for the explanation.
The problem can be reduced to a similar problem as below:
Given a 2D array. Some cells are empty and some cells contain number L_{ij}. We can make two kinds of operation:
- Increase all the non-empty numbers in some row i by P_i (P_i \ge 0)
- Decrease all the non-empty numbers in some column j by Q_j (Q_j \ge 0)
So for each cell (i,j) the new value will be
W_{ij} = L_{ij} + P_i - Q_j
You also have two more 2D arrays S and T as the upper and lower bound of the new array W. Such that S_{ij} \le W_{ij} \le T_{ij}.
Your target is to maximize sum of W_{ij}, i.e, Maximize L_{ij} + P_i - Q_j
You also need to print P_i, Q_j.
Solution:
Let’s formulate primal-simplex.
Let, sizeRow(i) = number of non-empty cells in row i. Also sizeCol(j) is defined similarly.
So our objective function is:
Maximize: sum(P_i * sizeRow(i)) - sum(Q_j * sizeCol(j)) [we are omitting constant: sum(L_{ij})]
Constraints:
S_{ij} \le L_{ij} + P_i - Q_j \le T_{ij}
Or both of them boil down to:
P_i - Q_j \le Constant or Q_j - P_i \le Constant.
So our constraint inequality: Ax \le B will have one special properties:
*Every row of A has one +1, and one -1. Other than that every thing is normal.
Now dual time.
Objective function: minimize B*y [you will see in a moment that B is acting as cost of a flow network and y is the flow variables of the arcs]
Constraints:
A' * y \ge column\_matrix[sizeRow(1), ...., -sizeCol(1), ...]
In A' now we have one +1 and one -1 in each column. So if you sum all the in-equalities you will get 0 in left side. Right side it’s also 0. So all the \ge are actually =.
Now consider, all the columns of A' as directed edge (from say -1 to +1) and all the rows as vertex. Then you will find: sum(in flow) - sum(out flow) = const. Which is flow-conservative-equation. If the right side is say negative we have demand (arc to sink) and if positive then we have supply (arc from source). We have the cost of those flow in objective function.
So finally we are to solve min-cost maxflow problem.
One thing,
One might wonder, why suddenly constraints changed from \ge to = in dual. What is the effect of such change in primal? Primal-dual conversion table says, it means the variable in primal is unconstrained.
Why its so?
Our operation was: increase in row, decrease in column.
But it gives the liberty to decrease row / increase column too. Suppose you want to decrease a row with only original operations: you can decrease all the columns and then increase other rows.
also can try to understand too