PROBLEM LINK:Author: Shiplu Hawlader 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: 1. Increase all the nonempty numbers in some row $i$ by $P_i$ ($P_i \ge 0$) 2. Decrease all the nonempty 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 primalsimplex. Let, $sizeRow(i)$ = number of nonempty 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 inequalities 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 flowconservativeequation. 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 mincost 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? Primaldual 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. AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 14 Jun '15, 00:01

This Editorial is only for those who already know how to solve the problem so, please give some more detailed editorial or otherwise remove it too.. answered 15 Jun '15, 20:47

please explain in detailed please so learner(beginner)like me ):P also can try to understand too answered 20 Jun '15, 22:19
