PROBLEM LINK:
Practice
Author: Jatin Yadav
Tester: tncks0121
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Flow decomposition theorem, Min cut max flow theorem.
PROBLEM:
There are n friends. The i^{\text{th}} has A_i coins. A single transaction is defined as a transfer of one coin from one friend to another.
Between every ordered pair (i, j) there can be a maximum of R transactions of one coin from i to j. What is the maximum possible value of minimum number of coins a friend has in the end of the transactions?
QUICK EXPLANATION:
WLOG, assume the array A to be sorted. Let T_i = \displaystyle \sum_{j=1}^{i} A_j. The answer is then T = \displaystyle \min_{i = 1}^{n} \left \lfloor \dfrac{ Ri (n - i) + T_i}{i} \right \rfloor.
EXPLANATION:
Clearly, T is an upper bound on the ans. This is because the maximum number of coins that can be transfered from others to the first i friends is Ri(n - i), so the first i friends can’t have more than P_i + Ri(n-i) coins in total. So, the minimum of the coins among the first i friends must be \leq \left \lfloor \dfrac{ Ri (n - i) + T_i}{i} \right \rfloor.
We have to prove that this value is indeed achievable.
Lets say we want to make the minimum \geq P. Consider the following flow graph:
- For each i there is an edge from source to it of capacity \max(0, A_i - P)
- For each i there is an edge from it to sink of capacity \max(0, P - A_i)
- For each ordered pair (i, j), there is an edge of capacity R from i to j.
Let Z = \displaystyle \sum_{i=1}^{n} \max(0, P - A_i)
The flow from source to a node i represents the net decrement in the number of coins of friend i. Since each node with A_i \geq P can transfer a maximum of \leq A_i - P coins, we have this much capacity from source to this node.
The flow from a node to sink represents the net increment in the number of coins of friend i. The amount of flow from i to sink must be atleast \max(0, P - A_i), which is also the capacity.
The flow between two friends represents the amount transfered from one to the other.
Claim: A min value \geq P can be achieved iff the max flow in the above described flow graph is equal to Z.
Proof:
We use the Flow Decomposition Theorem, which states that any s-t flow can be decomposed into s-t paths and cycles.
(\Longrightarrow) Say P is achievable. In the sequence of transactions, say f_{ij} is the total amount transacted from i to j. For each i whose number of coins decrease, let f_{si} be the decrement. For each i whose number of coins increase, let f_{it} be the increment. Then, f is an almost valid flow (The incoming and outgoing flows are equal at each node. The capacity constraints for the edges except those going into the sink are satisfied.). If some i \rightarrow t edges are overflowing, we can decompose the flow and remove some paths to get a valid flow.
( \Longleftarrow ) Say we have a flow with the required value. Decompose it into paths. Pass a single coin along each path. Each edge has transaction equal to flow through it which is \leq R, and in the end everyone has \geq P coins.
Now, we clearly can’t run a max flow algorithm on this graph as it has n^2 edges which is too much. Instead, we use min cut max flow theorem. We have to partition the flow graph into two sets A, B, such that source s \in A, sink t \in B and the sum of capacity of edges going from A to B is minimized.
Say B = t \cup F, where F is the set of friends in B. Let |F| = i.
\overline{F} = \{1, 2, \ldots n\} \setminus F is the set of friends in A. The amount of A-B cut would be:
\underbrace{R (n-i)i}_{\overline{F} \rightarrow F} + \displaystyle \sum_{j \in \overline{F}} \underbrace{ \max(0, P - A_j)}_{j \rightarrow t} + \displaystyle \sum_{j \in F} \underbrace{ \max(0, A_j - P)}_{s \rightarrow j}
= R i (n-i) + \displaystyle \sum_{j = 1}^{n} \max(0, P - A_j) + \displaystyle \sum_{j \in F} (\max(0, A_j - P) - \max(0, P - A_j))
= R i (n - i) + Z + \displaystyle \sum_{j \in F} (A_j- P)
This means that, min cut \geq Z if and only if, for each i, \displaystyle \sum_{j \in F} A_j + Ri(n-i) \geq P i for all sets F of size i.
This is equivalent to : P \leq \dfrac{T_i + Ri(n-i)}{i} for all i. Clearly if P satisfies this inequality, we get a min cut \geq Z, and P is achievable as the minimum.
So, \displaystyle \min_{i} \left \lfloor \dfrac{T_i + Ri(n-i)}{i} \right \rfloor is the optimum value.