Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

input: $b_1,b_2,...,b_n$ positive integers. $a_1<a_2<...a_n$ positive integers output: positive integer

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.

share|improve this question
1  
This is very closely related to this question. If you're the same user, this is very bad style; you should have linked to the related question and explained the difference between them, or at the very least asked them from the same account instead of forcing people to find the other one by a general search. If you're not the same user, how come you have such a similar user name and asked such a similar question? –  joriki Dec 2 '12 at 15:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.