Problem LinkAuthor: Aleksa Plavsic Tester: Mark Mikhno Editorialist: Bhuvnesh Jain DifficultyMEDIUMHARD PrerequisitesBinary Search ProblemYou 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$. ExplanationThe 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:
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.
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.
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)
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.
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 subrectangle 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 subrectangle 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.
This is similar to the case $1$ and is left as an exercise.
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 subrectangles 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 subrectangle. If value $W$ is greater than it, then we can safely ignore such subrectangles. If value $W$ is less than $a$, then we can ignore the subrectangles containing $b$ and $c$ as we subrectangle containing $a$ might contain $W$ and since rows and columns are increasing, the other $2$ subrectangles 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 subrectangles 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 subrectangle 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 subrectangle and then solving subrectangle. 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 subrectangles 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. asked 19 Aug '18, 13:37

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. answered 19 Aug '18, 16:53
1
Corrected.
(19 Aug '18, 17:46)
1
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.
(19 Aug '18, 18:27)
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.
(19 Aug '18, 18:44)
1
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.
(20 Aug '18, 02:41)

Something strange is happening. 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. 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)) answered 21 Aug '18, 04:09

Where is the function "SolveSubRectangle"?
@meoow, the links were not correct. Updated.