Week5; Constructive Thinking example

Lin Myat Ko
Jul 30, 2017 · 3 min read

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?

Sorry, it’s inverted.

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.

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.

Lin Myat Ko

Written by

Full Stack Engineer. I am Light. I am confident with full self-esteem. I know what I don't know and I keep learning to solve. I will not falter, nor give up!

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade