INMAT - Editorial

editorial
, , , , ,
1

Problem Link

Practice

Contest

Author: Aleksa Plavsic

Tester: Mark Mikhno

Editorialist: Bhuvnesh Jain

Difficulty

MEDIUM-HARD

Prerequisites

Binary Search

Problem

You are given a matrix with of size N * N. Each row and column is either sorted in increasing or decreasing order and all the numbers in the matrix are distinct. You can ask ask at most K questions of the form (i, j) where you get the output as A[i][j], the element at that position in the matrix. You need to find where does the element W exist in the matrix and it doesn’t exist, output -1.

Explanation

The first 2 subtasks can be easily solved with binary search. For this, simply query the first and last element of each row. This indicates whether the row is sorted in increasing or decreasing order. Now, simply binary search over the elements in every row. This takes at most (ceil(\log{N}) + 2) operations for every row. You can optimize this a bit more by applying binary search for rows for which the W already lies in the range for the initial 2 elements asked for that row.

To proceed towards the full solution, let us first understand a bit more about the structure of the matrix. we have the following theorems:

  • Let say we denote increasing columns by U and decreasing columns by V. If two consecutive columns differ have different type i.e. U and V, then there is a change in the type of columns. If this change occurs more than once then all the rows must be either increasing or decreasing. The same applies to the case of rows as well.

Proof

Let us consider a 3 X 3 matrix as below:

\begin{bmatrix} a & b & c \\ e & f & g \\ i & j & k \end{bmatrix}

Since there occurs a change in the type of columns more than once, we assume columns are U V U i.e.

  1. a < d < i
  2. b > e > j
  3. c < f < k.

To show all rows should be either increasing or decreasing, consider the case when row 1 is increasing. This means a < b < c. Assume on the contrary that row 2 is decreasing. So, we have b > f > e > a. This is a contradiction to claim that row 1 in increasing.

If row 3 was decreasing, then we have b > j > k > c, which is again a contradiction to fact that row 1 is increasing. Thus, if row 1 is increasing all rows must be increasing. Similarly, we can prove for the case for decreasing row 1.

The other case of columns being V U V can be proved on similar terms.

Using the proof idea for a matrix 3 X 3, we can extend the idea to higher dimensions and consider smaller 3 X 3 matrices in them (either consider continuous same type columns/rows as a block) to show either all rows/columns will be increasing.

  • If all the rows or columns are not of the same type then the matrix is of the special type, which is extended from a 2 X 2 matrix.

The idea for this is based on the above prove which required a matrix of size atleast 3 X 3 as we needed atleast two changes in column/row types. Let us consider a 2 X 2 matrix.

\begin{bmatrix} a & b \\ c & d \end{bmatrix}

All 16 possibilities are there: (Construct examples on your own for better understanding)

  1. a < b, c < d, a > c, b > d.
  2. a < b, c < d, a > c, b < d.
  3. a < b, c < d, a < c, b > d.
  4. a < b, c < d, a < c, b < d.

and so on …

We simply extend this 2 X 2 matrix to a N X N matrix where there is exactly one change in the row and column types. The idea is as follows

But while extending from 2 X 2 to N X N matrix, we have only two possibilities. Either both row 1 and column 1 are increasing or both are decreasing. They can’t have the different type. The proof (using 4 X 4 matrix) is below:

\begin{bmatrix} a_1 & a_2 & a_3 & a_4 \\ a_5 & a_6 & a_7 & a_8 \\ a_9 & a_{10} & a_{11} & a_{12} \\ a_{13} & a_{14} & a_{15} & a_{16} \end{bmatrix}

Assume row 1 is decreasing and column 1 is decreasing. The type of row and column both changes at 2. So, the row types are (V, V, U, U) and column types are (U, U, V, V).

Using the types of rows and columns, we have a_7 < a_6 < a_5 < a_9 < a_{10} < a_{11}. But it is a contradiction to fact that a_7 > a_{11} as column 3 is decreasing. Thus, the proof is done. (The main idea of the proof is to start moving from an element in increasing direction till you reach one for which result is known and you get a contradiction. This helps us to extend it for N X N matrix as well).

So, there are only 3 types of matrices possible if all the rows and columns are sorted in some order. Great, this also gives some ideas on how to create test cases as well. (If you didn’t get it, try again after reading the above proofs).

To proceed further, we need to intelligently find the type of every row and column in the minimum number of queries. The minimum number cannot be less than 2 * N as for every row we need to query atleast 2 elements to determine its type. But if these 2 * N queries are done intelligently then we can know the type of columns as well. Below is two such technique.

Remember, we have used 2 * N queries till now.

Now, I will describe how to deal with different matrices.

  • Case 1: All rows are increasing or decreasing

Let us iterate the columns from left to right and group them by their type, i.e. considering all consecutive increasing/decreasing columns together. Based on whether columns are increasing or decreasing, select the row. It can be either row 1 or N. If for that row and column range, the numbers have W in their range, we have found a valid sub-rectangle which is the possible candidate to contain W. Note that since we are iterating over columns in increasing order and not doing a binary search. So, if the previous columns were ignored, it means their value was either less or greater than W. So, only the other condition is required to be checked.

Thus, we find a suitable sub-rectangle in which all rows and columns are of the same type and it is the possible candidate to contain W. We use N queries in this step in the worst case. The further solution will be explained later.

  • Case 2: All columns are increasing or decreasing

This is similar to the case 1 and is left as an exercise.

  • Case 3: All rows and columns change their type exactly once

For this, consider the above image shown. We will query the points a, b, c, d first. This will help us determine the type of every four sub-rectangles highlighted. I will show some cases on how to proceed further. (Rest is left as an exercise or can be looked by in the solution)

Assume, both row 1 and column 1 are increasing. This means both a and d will be the largest element in their sub-rectangle. If value W is greater than it, then we can safely ignore such sub-rectangles. If value W is less than a, then we can ignore the sub-rectangles containing b and c as we sub-rectangle containing a might contain W and since rows and columns are increasing, the other 2 sub-rectangles already exceed in values as compared to W. Other cases can be handled similarly.

So, after this process as well, we get at most 2 candidate sub-rectangles which can contain W. Both of them have the property that all rows and columns are either increasing or decreasing.

Thus, in all the above cases, we have a sub-rectangle to query such that all rows and columns in it are either increasing or decreasing. Using the above property, ask at most N questions to find if W exists or not. The strategy for this is explained in the solution. Please refer to the function SolveSubRectangle for more details.

Last caveat:

For the cases 1 and 2 the questions asked were 2 * N + N + N, where initial is for determining the type, then for finding sub-rectangle and then solving sub-rectangle.

For the case 3, the questions asked were 2 * N + 4 + N + N, where initial is for determining the type, next 4 for a, b, c, d and last are for at most two candidate sub-rectangles which could be queried. For removing the above additional 4 queries, you can see that it will always be one of the cells which was already queried (see the algorithm for subrectangle and the idea of almost greatest element in solution). So, we need to ask a question for the cell if it was not asked before.

The solution is complete now and the complexity is O(K) as for each query we perform O(1) operation and also know which next cell to query in O(1).

The space complexity is O(N^2) to store the elements of the matrix.

For details, refer to the commented solution of the author (The original solution was written in his native language. I have translated it and added comments for help).

If your approach was somewhat different, please share it in the comments section below, but with proof on the number of queries.

Time Complexity

O(K)

Space Complexity

O(N^2)

SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

Editorialist’s solution can be found here.

2

Since there occurs a change in the type of columns more than once, we assume columns are UVU i.e.

Explain where is d and where is g used ??

Please correct typos.

1 Like
3

Something strange is happening.

As I type this, my firefox is showing the Author’s solution as pointing at http://www.codechef.com/download/Solutions/AUG18/setter/INMAT.cpp (probably from a revision of the editorial from yesterday)

But the intention is to point the Author’s solution at https://ideone.com/5m6n4Q

A more serious problem is that the solution from ideone can take about 5n steps to find the answer. This picture shows 96 queries to solve a 20x20 square.

alt text

The error is that the points following the curved lines are more numerous than necessary. It is sufficient to ask perform fewer queries, resulting in these 80 queries. (The red markers are larger than the target, black markers are smaller. The rows are decreasing with x, the columns are increasing with y. The final correct answer is the point at (15,1))

alt text

1 Like
4

Corrected.

5

The logic still looks wrong, and doesn’t need the complexity of proof by contradiction.

If the top row is increasing, then b \lt c, so we have f \lt b \lt c \lt g, which gives f \lt g showing that the second row in increasing.

If top row is decreasing, then a \gt b, so we have e \gt a \gt b \gt f, which gives e \gt f showing that the second row is decreasing.

Combining these cases, we have shown that both the top row and second row are increasing, or both are decreasing. Similarly the second and third rows are both increasing, or are both decreasing.

1 Like
6

Corrected @john_smith_3. Yes, direct proof also follows. I didn’t think about that, generally, try the proof by condratictions in case of inequalities as I find it easier to reason about.

7

Still not right. To match the matrix, the three numbered inequalities should read

a \lt e \lt i
b \gt f \gt j
c \lt g \lt k

The argument comparing row 1 and row 2 is wrong. It shows b \gt a, which doesn’t contradict row 1 increasing.

The argument comparing row 1 and row 3 is correct, though not really necessary. Having shown that row 1 increasing implies row 2 increasing, a repeat shows row 2 increasing implies row 3 increasing. It would be more interesting to give the argument that row 1 decreasing implies row 2 decreasing.

1 Like
8

Where is the function “SolveSubRectangle”?

9

@meoow, the links were not correct. Updated.

10

Is it fixed now?