Largest sum of upper-left quadrant of matrix that can be formed by reversing rows and columns

Question

I'm working on a HackerRank problem that's finding the largest sum of the elements in upper-left quadrant of a 2N x 2N matrix after reversing rows and columns. For example, if the matrix is

M = [
  112  42   83   119
  56   125  56   49
  15   78   101  43
  62   98   114  108
];

then the largest sum that can be formed from reversing rows and columns is 119 + 114 + 56 + 125 = 414 after getting the matrix

M' = [
   119  114  42   112
   56   125  101  49
   15   78   56   43
   62   98   83   108
];

from reversing column 2 and then row 0.

I have not figured out an easy solution, but I have come up with some facts that might be helpful:

• It is not possible to get any configuration from reversing rows and columns. Therefore, the answer cannot be to simply sort all the elements and sum the top NxN of them.
• Furthermore, it is not possible to move any 1 element to any other position. For example, the only possibly places for the element at (N-1,N-1) to be moved are (0,N-1),(N-1,0),(0,0).
• It requires 1 row reversal to get an element from the upper-right or bottom-left quadrant to the upper-left quadrant, and 2 reversals to get an element from the bottom-right quadrant to the upper-left quadrant.
• It's not possible to come up with a solution that simply looks at each element in the upper-left quadrant and checks whether it can be replaced by a larger element in the range of elements that can be moved in it's place (e.g. M[0,1]=42 can be replaced by M[0,2]=83 or M[3,2]=114 or M[3,1]=98) because you have to also consider the other elements that get dragged along in the process.

Other than those facts, I cannot think of anything that helps me construct a simple solution. Is there any obvious fact that I am missing? I stayed up past midnight thinking about this last night. :)

Answer 1

Let's develop your observation about the fact that an element (N - 1, N - 1) can be only in (0, 0), (N - 1, 0) or (0, N - 1) position.

• Consider an (r, c) element. One can observe that it can only be in one of the following four positions: (r, c), (N - r - 1, c), (r, N - c - 1) or (N - 1 - r, N - 1 - c)

• One can show that there is always a sequence of operations that places the largest of the four numbers located in the vertices of the rectangle described above to the upper-left quadrant without changing the rest of it (to prove it, one can just consider all cases and provide an explicit construction to do it. It's quite long but straightforward, so I'll not post it here).

• These two observation give the following solution:

  int sum = 0;
  for (int i = 0; i < n / 2; i++)
      for (int j = 0; j < n / 2; j++)
          sum += max(a[i][j], a[i][n - j - 1], a[n - i - 1][j], a[n - i - 1][n - j - 1]); 
  

Answer 2

find the maximum upper-left-quadrant Sum value of the values of the cells, for a square matrix.

The key point here is that every cell in a square matrix can be replaced with only 3 other cells (by reversing a line, or a column - by transposing the matrix, reversing the line, and then transposing again), hence to calculate (without changing the matrix) the max value of the upper-left-quadrant, we only need to calculate the max value possible for every cell in the upper-left-quadrant.

1. In the (double) 'for' loop:

• scanning the upper-left-quadrant cells,
• fo each cell, comparing its value with the other 3 available-for-replacement values.
• using '//' to receive an int ('/' will give a float)

2. In the following 'Sum += ..' code:

• We can add the current cell [i, j] value (from the upper-left-quadrant) to the sum,
• or, add other cell value, for any cell that can be replaced with [i, j] within the matrix.
• Any cell in a square matrix can be replaced with only 3 other cells,
• hence, we choose the max value between the cell itself and the other 3.

def maxSum(mat):
    R = C = len(mat)
    Sum = 0

    for i in range(0, R // 2):
        for j in range(0, C // 2):
            r1, r2 = i, R - i - 1
            c1, c2 = j, C - j - 1

            Sum += max(mat[r1][c1], mat[r1][c2],
                       mat[r2][c1], mat[r2][c2])

    return Sum


# Testing
if __name__ == "__main__":
    mat = [[112, 42, 83, 119],
           [56, 125, 56, 49],
           [15, 78, 101, 43],
           [62, 98, 114, 108]]

    print(maxSum(mat))  # 414
    exit()