Bart set up a circular poker table for his friends so that each of the seats at the table has the same number of poker chips. But when Bart wasn’t looking, someone rearranged all of the chips so that they are no longer evenly distributed! Now Bart needs to redistribute the chips so that every seat has the same number before his friends arrive. But Bart is very meticulous: to ensure that he doesn’t lose any chips in the process, he only moves chips between adjacent seats. Moreover, he only moves chips one at a time. What is the minimum number of chip moves Bart will need to make to bring the chips back to equilibrium?
Example
For chips = [1, 5, 9, 10, 5], the output should be
pokerChips(chips) = 12.
The array represents a circular table, so we are permitted to move chips between the last and the first index in the array. Thus Bart can bring the chips back to equilibrium with the following steps (1-indexed):
- move 2 chips from seat 2 to seat 1 (2 moves);
- move 3 chips from seat 3 to seat 2 (3 moves);
- move 3 chips from seat 5 to seat 1 (3 moves);
- move 4 chips from seat 4 to seat 5 (4 moves).
After this sequence of 12 moves, each seat will have 6 chips, and there is no sequence of fewer moves doing the same.
Input/Output
[execution time limit] 4 seconds (py)
[input] array.integer chips
The chip counts of each seat.
Guaranteed constraints:
0 ≤ chips.length ≤ 106,
0 ≤ chips[i] ≤ 100.[output] integer
The minimum number of moves required to restore the chip counts.
Solution
We have a table with \(n\) persons. Each person should have \(m\) chips, but accidentally every person got \(\mathbf{c}_i\) chips and our aim is to restore equilibrium with the least swaps. A swap can be made only with a direct neighbor on the table and only one chip at a time can be exchanged. It is obvious that \(m=\frac{1}{n}\sum\limits_{i=1}^{n}\mathbf{c}_{i-1}\) for the zero-indexed vector \(\mathbf{c}\).
We now define the overplus between two persons as flow, where a positive flow means moving chips to the right and negative flow means getting chips from the left. This means \(\mathbf{f}_0\) flows from the last person \(\mathbf{c}_{n-1}\) to the first person \(\mathbf{c}_0\), \(\mathbf{f}_1 := \mathbf{f}_0 + \mathbf{c}_0 - m\) flows from \(\mathbf{c}_0\) to \(\mathbf{c}_1\), \(\mathbf{f}_2 := \mathbf{f}_0 + \mathbf{c}_0 - m + \mathbf{c}_1 - m\) flows from \(\mathbf{c}_1\) to \(\mathbf{c}_2\) and so on. This shows, that the important information is, how much flow is passed between the first and the last person. This value has to be optimal in the sense that it minimizes the total flow. When we say that the zero-indexed flow vector \(\mathbf{f}\) describes the number of chips that must be moved from person \((i-1)\bmod n\) to person \(i\), we can define a cost function, which shall be used to optimize for \(f_0\):
\[g(f_0; \mathbf{d}) = \sum\limits_{i=1}^{n} |\mathbf{f}_{i-1}|\]
Now each person \(i\) gets \(\mathbf{f}_i\) chips from left and hands \(\mathbf{f}_{(i+1)\bmod n}\) to the right. From the definition of \(\mathbf{f}_i\) and the definition of the difference vector \(\mathbf{d}\) being \(\mathbf{d} = m - \mathbf{c}\) follows
\[\begin{array}{rrl} &\mathbf{d}_i &= \mathbf{f}_i - \mathbf{f}_{(i+1)\bmod n}\\ \Leftrightarrow&\mathbf{f}_{(i+1) \bmod n} &= \mathbf{f}_i - \mathbf{d}_i \end{array}\]
Putting this knowledge into our cost function yields
\[\begin{array}{rl} g(f_0; \mathbf{d}) &= |\mathbf{f}_0| + |\mathbf{f}_1| + \dots + |\mathbf{f}_{n-1}|\\ &= |\mathbf{f}_0| + |\mathbf{f}_0-\mathbf{d}_0| + \dots + |\mathbf{f}_{n-1}-\mathbf{d}_{n-1}|\\ &= |\mathbf{f}_0| + |\mathbf{f}_0-\mathbf{d}_0|+|\mathbf{f}_0-\mathbf{d}_0-\mathbf{d}_1| + \dots + |\mathbf{f}_{0}-\sum\limits_{i=0}^{n-2}\mathbf{d}_{i}| \end{array}\]
This is interesting. We know already from here how to minimize a sum of absolute values: Using the median! Therefore
\[\begin{array}{rl} \mathbf{f}_0 &= \text{median}({0, \mathbf{d}_0, \mathbf{d}_0+\mathbf{d}_1, \mathbf{d}_0+\mathbf{d}_1+\mathbf{d}_2,\dots , \mathbf{d}_0 + ... + \mathbf{d}_{n-2}) }) \end{array}\]
Putting \(\mathbf{f}_0\) now back into \(g\) calculates the minimal number of swaps.
Python Implementation
The mathematical derivation can be implemented in Python quite easily:
import numpy as np
def pokerChips(chips):
a = np.array(chips)
s = np.cumsum(a - a.mean())
return np.abs(s - int(np.median(s))).sum()