wu :: forums « wu :: forums - Reverse signs for positive row col sum in an array » Welcome, Guest. Please Login or Register. Oct 31st, 2024, 4:04pm

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    cs (Moderators: Eigenray, Grimbal, ThudnBlunder, william wu, Icarus, SMQ, towr)    Reverse signs for positive row col sum in an array « Previous topic | Next topic » Pages: 1  Reply Notify of replies Send Topic Print    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 towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: Reverse signs for positive row col sum in an a   « Reply #1 on: Jan 1st, 2012, 10:27pm » Quote Modify Something like the solution for http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs; action=display;num=1253641163 might work.. « Last Edit: Jan 1st, 2012, 10:29pm by towr » IP Logged Wikipedia, Google, Mathworld, Integer sequence DB 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 Pages: 1  Reply Notify of replies Send Topic Print Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board