input: $b_1,b_2,...,b_n$ positive integers. $a_1
I'm given
$b_1$ columns of the form $\left( \begin{array}{ccc} 1 \\ 0 \\ 0 \\ .\\ .\\ .\\ 0 \end{array} \right) $ $b_2$ columns of the form $ \left( \begin{array}{ccc} 0 \\ 1 \\ 0 \\ .\\ .\\ .\\ 0 \end{array} \right) $ … $b_n$ columns of the form $\left( \begin{array}{ccc} 0 \\ 0 \\ 0 \\ .\\ .\\ .\\ 1 \end{array} \right) $ and $b_1+...+b_n$ zero columns. With these columns several $n\times 2(b_1+...+b_n)$ matrices can be made. Notice that those matrices will have at most one '1' in each column.
$a_1,...,a_n$ are positions in rows 1,2 etc. For example $a_1$ is the position $(1,a_1)$.
I'd like to keep every '1' in each row as close as possible to the given $a_{row}$.
What is the best possible minimum distance I can have? To be precise, there is a Matrix that the maximum distance (some '1' has from $a_{row}$) is the minimum of all the other maximum possible distances of all the other Matrices. What is that distance?
I'm not interested in the Matrix that will give me that minimum distance only in the distance itself. Is there an efficient algorithm that computes it?
$ \left( \begin{array}{ccc} 1 & 1 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&1\end{array} \right) $ for $a_1=2,a_7=6$ Is a Matrix with the property we want, as is the following one $\left( \begin{array}{ccc} 0 & 1 &1 & 0 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&1\end{array} \right) $
distance here is 1 on the contrary the following matrix is not
$ \left( \begin{array}{ccc} 1 & 0 &0 & 1 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&0\\ 0 & 0 &0 & 0 &0&1\end{array} \right) $ here the distance is 2.