INMAT - how many queries are needed?

general
, ,
1

Problem Link

practice

Given a hidden n by n matrix of integers, in which every row and every column is strictly increasing or decreasing, query individual squares to find a given target value, or determine that the target value is not in the matrix.

Question

How many queries are needed to solve the INMAT problem?

Thought 1

There cannot be a solution that is guaranteed to take less than 2n queries.

By way of example, take n to be 5, and the hidden matrix to be

\left( \begin{array}{ccccc} 10 & 21 & 32 & 43 & {\bf 54} \\ 20 & 31 & 42 & {\bf 53} & {\bf 63} \\ 30 & 41 & {\bf 52} & {\bf 62} & 72 \\ 40 & {\bf 51} & {\bf 61} & 71 & 81 \\ {\bf 50} & {\bf 60} & 70 & 80 & 90 \end{array} \right)

It the target is 55, then any of the 9 bold numbers could be replaced by 55, still resulting in a matrix in which every row is increasing left to right, and every column is increasing top to bottom. So one cannot be certain that 55 is not in the matrix before all 9 bold entries have been queried. At least one more query is needed to determine the orientation of the bold stripe.

For a general n, we can construct a matrix with n elements on the diagonal, and n-1 elements on the neighbouring diagonal. All 2n-1 elements have to be queried before we can be sure there is no solution.

Thought 2

A reasonable solution can be made by recursively dividing the matrix into rectangles, and querying the corners when necessary at each step. Taking the example above, still with target 55, sample the four corners:

\begin{array}{ccccc} 10 & x & x & x & 54 \\ x & x & x & x & x \\ x & x & x & x & x \\ x & x & x & x & x \\ 50 & x & x & x & 90 \end{array}

Divide the grid into the left 3 columns, and the right 3 columns. Without querying, we can tell that the cell containing 32 has value between 10 and 54, so is less than the target. Use L to indicate less than the target. So we now have

\begin{array}{ccc} 10 & x & L \\ x & x & x \\ x & x & x \\ x & x & x \\ 50 & x & 70 \end{array} \quad {\text{and}}\quad \begin{array}{ccc} L & x & 54 \\ x & x & x \\ x & x & x \\ x & x & x \\ 70 & x & 90 \end{array}

Divide each rectangle top and bottom. One of the new corners is already known to have value less that the target, so we have

\begin{array}{ccc} 10 & x & L \\ x & x & x \\ L & x & 52 \end{array} \quad\quad \begin{array}{ccc} L & x & 54 \\ x & x & x \\ 52 & x & 72 \end{array} \\ {\text{and}} \\ \begin{array}{ccc} L & x & 52 \\ x & x & x \\ 50 & x & 70 \end{array} \quad\quad \begin{array}{ccc} 52 & x & 72 \\ x & x & x \\ 70 & x & 90 \end{array}

The top left rectangle can be eliminated, because all 4 corners have value less than the target. Further subdivision of the other squares is needed. In the end, the values that will have been queried are

\begin{array}{ccccc} 10 & x & x & x & 54 \\ x & x & x & 53 & 63 \\ x & x & 52 & 62 & 72 \\ x & 51 & 61 & x & x \\ 50 & 60 & 70 & x & 90 \end{array}

A total of 13 queries are needed for the 5 by 5 matrix.

Experimentally I find that the technique uses about 3n steps for this sort of test case.

1 Like