Saturday, May 2, 2009

Rom/Column Inversion

You are given a matrix m*n (need not be square) of positive/negative integers. The only operations permitted are you invert the signs of an entire row or an entire column. And that is counted as one step. The goal is the to reach the maximum sum possible (of all elements) of the matrix with such a series of operations. 

Q. Does the process converge. If yes, then what is the complexity ?

Clue: When would you do such an operation ? And when you do that what happens to the total sum? What is the max sum which can be reached. 

No comments:

Post a Comment