1
$\begingroup$

So here is the challenge problem statement: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1512

Basically, given a 0/1 matrix, you need to permute the columns so that the first column is fixed and after the permutation of columns, then for each row the 1's in the row occur contiguously (without counting wrap-around). I thought about this problem and came up with a conjecture that would make it easy to solve, but I'm not sure if it's true.

Conjecture: After the first $k$ columns have been chosen, let $S$ be the set of rows that end with a $1$ in the $k$th column, such that there exists an unchosen column that has a $1$ in that row. Then the $k+1$th column can be chosen to be the column that has (i) 1's for all positions in $S$, and (ii) which has a minimum total number of $1$'s.

Is this true? If so an optimal solution could be constructed very quickly. I know that the $k+1$th column has to satisfy condition (i), which reduces the possibilities, but I'm really hoping we can ensure condition (ii) also holds so that the choice of $k+1$th column is essentially unique.

$\endgroup$
  • $\begingroup$ Please copy the relevant part of the problem to the body of your question. $\endgroup$ – Yuval Filmus Apr 21 '14 at 18:32
  • 1
    $\begingroup$ Your conjecture is probably false. The best way to disprove it is to write this algorithm up and test a few random examples. Only if the algorithm does seem to work I would suggest trying to prove it. $\endgroup$ – Yuval Filmus Apr 21 '14 at 18:34
  • $\begingroup$ It looks like cs.stackexchange.com/q/23957/755 has a better description of the problem but this has a more specific question (so this question is more suitable for this site). You might like to refer to that question to improve the description of the problem in this question. $\endgroup$ – D.W. Apr 21 '14 at 20:44
  • $\begingroup$ @YuvalFilmus I have a feeling that random matrices (fill each row with a randomly sized subset of contiguous 1's, and then permute columns) may lead to an impression that the algorithm works even though it fails in some exotic corner cases. However, if no one has a better suggestion, I'll do as you suggest and see what happens and report back with the results. $\endgroup$ – user2566092 Apr 21 '14 at 20:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.