Author |
Topic: Reverse signs for positive row col sum in an array (Read 4085 times) |
|
Dufus
Newbie
Posts: 43
|
|
Reverse signs for positive row col sum in an array
« on: Jan 1st, 2012, 8:19pm » |
Quote Modify
|
I sometimes back stumbled upon this puzzle (I couldnt find a similar problem on this forum). It goes like this.. Given an mxn 2D array of real numbers and permitted, at any time, to reverse the signs of all the numbers in any row or column. 1. Prove that you can arrange matters (terminology used by the puzzle source), so that all the row sums and column sums are non-negative. 2. What exactly would be that algorithm?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Reverse signs for positive row col sum in an a
« Reply #2 on: Jan 2nd, 2012, 5:52am » |
Quote Modify
|
The obvious method would be to - reverse signs in each row with negative sum - reverse signs in each column with negative sum. - repeat until no more negative sum is found. It can not loop forever because at each step you increase the total sum of the matrix. So it is bound to stop. I guess it is O(m*n*(m+n)).
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Reverse signs for positive row col sum in an a
« Reply #3 on: Jan 7th, 2012, 2:30am » |
Quote Modify
|
on Jan 2nd, 2012, 5:52am, Grimbal wrote:The obvious method would be to - reverse signs in each row with negative sum - reverse signs in each column with negative sum. - repeat until no more negative sum is found. It can not loop forever because at each step you increase the total sum of the matrix. So it is bound to stop. I guess it is O(m*n*(m+n)). |
| Can you give your insights about its runtime ? Why did you guess O(m*n*(m+n)) ?
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Reverse signs for positive row col sum in an a
« Reply #4 on: Jan 9th, 2012, 2:18am » |
Quote Modify
|
m*n is one pass of checking each row and each column. And I guess that it won't take more than m+n passes. But it is just a guess. The more I think of it, the more I feel it could be wrong.
|
|
IP Logged |
|
|
|
|