Editorial for COCI '14 Contest 6 #5 Neo

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

It is crucial to see that the following statement holds: Matrix $A$ ~A~ is extremely cool if and only if every single one of its submatrices of dimensions $2 \times 2$ ~2 \times 2~ is cool.

Accordingly, we can construct a new matrix where the element located at $B[i][j]$ ~B[i][j]~ is set to $1$ ~1~ if $A[i][j]+A[i+1][j+1] \le A[i][j+1]+A[i+1][j]$ . Solving this task now comes down to searching for a maximum area rectangle in matrix $B$ ~B~ that consists of only $1$ ~1~s. We believe that this problem is quite familiar to the contestants, so we will not go into further analysis. Depending on the implementation complexity, it was possible to score $40\%$ ~40\%~, $60\%$ ~60\%~ or $100\%$ ~100\%~ of total points for time complexities $\mathcal O(n^4)$ ~\mathcal O(n^4)~, $\mathcal O(n^3)$ ~\mathcal O(n^3)~, $\mathcal O(n^2)$ ~\mathcal O(n^2)~, respectively.

We will prove the aforementioned statement using mathematical induction. First, let's write down the definition of a cool matrix as $A(1, 1)-A(1, s) \le A(r, 1)-A(r, s)$ ~A(1, 1)-A(1, s) \le A(r, 1)-A(r, s)~.

We prove the weaker statement: Matrix $A$ ~A~ of dimensions $2 \times s$ ~2 \times s~ is extremely cool if every single one of its submatrices of dimensions $2 \times 2$ ~2 \times 2~ is cool.

We conduct the induction on $s$ ~s~.

Base: $s = 2$ ~s = 2~, it holds because every $2 \times 2$ ~2 \times 2~ cool matrix is extremely cool.

Step: We assume that there is an $s$ ~s~ such that the statement holds. Let's notice what happens then with a matrix of dimensions $2 \times (s+1)$ ~2 \times (s+1)~.

Since every $2 \times 2$ ~2 \times 2~ submatrix is cool if it holds $A(1, s)-A(1, s+1) \le A(r, s)-A(r, s+1)$ , while from the step presumption we know that $A(1, s')-A(1, s) \le A(r, s')-A(r, s)$ ~A(1, s')-A(1, s) \le A(r, s')-A(r, s)~ for each $s' < s$ ~s' < s~. If we sum these inequalities, we get $A(1, s')-A(1, s+1) \le A(r, s')-A(r, s+1)$ for each $s' \le s$ ~s' \le s~.

We conclude that if the statement holds for a matrix of dimensions $2 \times s$ ~2 \times s~, then it must hold for a matrix of dimensions $2 \times (s+1)$ ~2 \times (s+1)~. In other words, by using the principle of mathematical induction, we have proved that the statement holds for every $s \ge 2$ ~s \ge 2~.

Analogously, we can conduct this proof on rows in a way that we fixate two columns and conduct the induction on rows. The formal continuation of the proof is left as an exercise to the reader.

Comments

There are no comments at the moment.