Week5; Constructive Thinking example

What is Constructive Proof?
Constructive proof is used in constructive algorithm problems. In those problems, we need to make our own theorem, assumption, or deduction or whatever it is called before we try to solve it.
If we don’t constructive a strong proof to handle that problem, the solution algorithm will be very far away from achieving its objective. We can eliminate all other ways, all irrelevant cases if we find a theory. It’s one way of solving the problems.
I will show you an example of it today.
ANSWER SPOILERS AHEAD, PROCEED WITH OWN RISKS.
Sean invented a game involving a 2n x 2n matrix where each cell of the matrix contains an integer. He can reverse any of its rows or columns any number of times, and the goal of the game is to maximize the sum of the elements in the n x n submatrix located in the upper-left corner of the 2n x 2n matrix (i.e., its upper-left quadrant).
by Voidminded
The above problem statement is excerpt from the link I give. This is the case study for today.
How do you think you will solve? Before any technical code execution, just try to think a plain old fashion pseudocode algorithm. How?
By brute-forcing? Or matrix manipulation or blah blah blah? Or huge data-structures?
What if I tell you it’s simple actually? The beauty is hiding in the beast!
Have you played Rubik’s cube? If you try one before, you will know that corner pieces always stay in corners, middle pieces always stay in middles and center pieces in centers, obviously! Middle piece can’t go to corner, vice visa. In rubik cube, if you understand the algorithms, you can make any possible combination you want.
Think of the above problem as Rubik’s cube. The goal is to maximize upper left quadrant, right? What if I tell you, you can get any max number for corresponding point?

For the sake of simplicity, I make 4x4 matrix. The goal is maximize 2x2 upper left Q. Like Rubik cube, there are corresponding pieces for corresponding position. Explanation,
for pt (0,0), there are four possible candidates. I painted them.
for pt(0, 1), same too.
for pt(1, 0), same too.
for pt(1, 1), same too.
I enlightened you, right?
Read editorial at hackerrank.com if you want to understand clearly.
Try to solve without reading it if you like. I’ve given you enough hints, I believe.
DISCLAIMER; THIS IS NOT A LESSON, NOT A SOLUTION. THIS IS JUST DESCRIBING MY THOUGHT PROCESS. THE INFORMATION OR ALGORITHM CONTAINED MAYBE WRONG. JUDGE AT YOUR OWN RISK.