In this example, SumC = (17, -4, -10, -9, -7) and SumR = (0, -9, -9, -4, 9).

We also define SumM = (sum of the elements in SumC) + (sum of the elements in SumR);

SumM is the "sum of the matrix". In this example, it is -26.

Then, we define two functions on this matrix:

void FlipSignCol(int);
void FlipSignRow(int);

FlipSignCol() takes an integer in (1..n) and changes the sign of all the numbers in that column. Doing so also results in changing one of the elements in SumC, all the elements in SumR, and also SumM. For example, calling FlipSignCol(1) on the array above yields (note zero based indexing):

[ 3 -1 -5 -3 4 ] [ 4 5 -2 -3 -3 ] [ 6 8 -2 -6 1 ] [ 3 -4 1 -4 -8 ] [ 1 -4 -2 7 -1 ] with SumC = (17, 4, -10, -9, -7), SumR = (-2, 1, 7, -12, 1), and SumM = -10.

Calling FlipSignRow() operates similarly on integers in (1..m).

Write a program to compute the minimum non-negative value of SumM that can be obtained by a succession of calls to FlipSignCol() and FlipSignRow() such that all values in SumC and SumR are also non-negative, and give the shortest possible sequence of such calls which achieves this value SumM while satisfying the non-negative property for all elements in SumC and SumR, given the following matrix: 33 30 10 -6 18 -7 -11 23 -6 16 -19 9 -26 -8 -19 -8 -21 -14 17 12 -14 31 -30 13 -13 19 16 -6 -11 1 17 -12 -4 -7 14 -21 18 -31 34 -22 17 -19 20 24 6 33 -18 17 -15 31 -5 3 27 -3 -18 -20 -18 31 6 4 -2 -12 24 27 14 4 -29 -3 5 -29 8 -12 -15 -7 -23 23 -9 -8 6 8 -12 33 -23 -19 -4 -8 -7 11 -12 31 -20 19 -15 -30 11 32 7 14 -5 -23 18 -32 -2 -31 -7 8 24 16 32 -4 -10 -14 -6 -1 0 23 23 25 0 -23 22 12 28 -27 15 4 -30 -13 -16 -3 -3 -32 -3 27 -31 22 1 26 4 -2 -13 26 17 14 -9 -18 3 -20 -27 -32 -11 27 13 -17 33 -7 19 -32 13 -31 -2 -24 -31 27 -31 -29 15 2 29 -15 33 -18 -23 15 28 0 30 -4 12 -32 -3 34 27 -25 -18 26 1 34 26 -21 -31 -10 -13 -30 -17 -12 -26 31 23 -31 -19 21 -17 -10 2 -23 23 -3 6 0 -3 -32 0 -10 -25 14 -19 9 14 -27 20 15 -5 -27 18 11 -6 24 7 -17 26 20 -31 -25 -25 4 -16 30 33 23 -4 -4 23 This is test data. Your entry will be graded on a matrix with different dimensions and values.

Download the test harness [.cpp] [.html]

To submit an entry please email your code within the body of an email to hdsubmit@hejl.com. No attachments, period. Multiple submissions are allowed, but please annotate the namespace with a submission number. Due date for entries is midnight on 10/31.

If you know a programmer who would be interested, forward the link! The listserv can be joined by sending a blank e-mail to hackers-join@hejl.com.

Have fun,

--hackers