13
$\begingroup$

Posted this on /r/puzzles too, none have given the right strategy as of now :)

There is a square grid of width and height $m$. Three facts about the grid:

  1. Each cell has a value, and no two cells have the same value.

  2. Each row and column is either ascending or descending.

  3. $1 \le m \le 1000$

You have to find some value v in the grid, (or see if it exists in the grid or not). What you can do: Ask an oracle for the value in a particular cell. But you can only ask a maximum of $4\times m$ questions to the oracle. What's your strategy?

For an easier version, try to solve it with around $m. \log(m)$ questions.

Best of luck!

Also, $4\times m$ doesn't necessarily mean that the puzzle can be solved in $4\times m$ questions for all $m > 1000$ ;)

PS: Row $i$ can be ascending, row $j$ can be descending, column $a$ can be ascending, $b$ can be descending etc, the entire grid isn't sorted, the rows and columns have their individual sorting.

$\endgroup$
  • $\begingroup$ For example, if m is equal to 3, we can ask 12 questions, though there are 9 grids. you will find v or not for sure... I think m is meant to be greater than some value like 4? $\endgroup$ – Oray Aug 7 '18 at 9:02
  • $\begingroup$ Is the strategy the same for odd and even values of $m$ ? Because I want to ask for the two diagonals, but this fails when $m$ is odd I think $\endgroup$ – Florian Bourse Aug 7 '18 at 9:07
  • $\begingroup$ @Oray The constraint on m is given, it can be upto 1000 $\endgroup$ – four_lines Aug 7 '18 at 10:05
  • $\begingroup$ @FlorianBourse Hmm, my approach with some change works for odd too. Post your idea for even below, I'll check it out :) (I'm OP btw, stupidly posted the question on a guest account) $\endgroup$ – four_lines Aug 7 '18 at 10:07
  • 1
    $\begingroup$ @four_lines you can merge accounts $\endgroup$ – Kruga Aug 7 '18 at 13:48
5
$\begingroup$

Partial answer (the idea to solve it by $O(M~log(M))$):

You may try to find the value independently for each row (or column). What you have to do is to use Binary Search Algorithm -- like to find a word in a dictionary -- on each row.

$\endgroup$
  • 1
    $\begingroup$ Right :) Now try for the harder version! $\endgroup$ – four_lines Aug 7 '18 at 10:08
2
$\begingroup$

Edit: There's a flaw in the answer below as pointed out in the comments, I will leave this here because some ideas might help other people (then again, maybe I'm on the wrong way)

I think the following strategy works, might be slightly off with roundings, but would probably be ok for m a power of 2:

First, query all the elements on both diagonals. This takes $2m$ queries, and is the fastest way to determine all the ordering in each row/column.
This restricts the value you're looking for in at most one of the 4 triangular quadrants defined by the 2 diagonals: up/left/right/bottom.
You're left with $2m$ queries and have to search in a triangle of basis $m-2$, and height $(m-2)/2$.
Then, we finish by an easy induction / binary search. We can cut the triangle in half with $(m-2)/2$, and have a rectangle triangle that you can cut with only $(m-2)/4$ queries. Then you're left with a triangle that is identical, but $4$ times smaller than the previous one, and repeat.
The cost in query of this induction is thus $\sum_i (m-2)/2^i$, which is less than $2m$

$\endgroup$
  • 3
    $\begingroup$ How can you determine the quadrant where the value resides? $\endgroup$ – w l Aug 7 '18 at 10:01
  • $\begingroup$ @wl pointed out a major flaw in your answer. Figuring out the ordering of each row and column isn't enough to tell in what row, column or quadrant the value is. For example, if you have: line1=1 ? 9, line2=? 4 ? and line3=11 ? 2, the number 3 can be on any exclamation mark (or absent). $\endgroup$ – xhienne Aug 7 '18 at 10:51
  • $\begingroup$ You're right, I was thinking on each row you'd end up with being either left middle or right, and the columns would help solving, but there are in fact possibilities where the number could be in any spot Another example that kills this strategy is a grid that is symmetric along both diagonals. I edited the answer to reflect the fact that it is flawed $\endgroup$ – Florian Bourse Aug 7 '18 at 11:09
1
$\begingroup$

I show a solution for

$m \in \{5,6\}$, that is the smallest $m$s where allowed number of questions ($4\times m$) is less than the number of cells.

First,

query the $2\times m$ cells on the main diagonal and another 'parallel' translated diagonal which starts in the $\lceil\frac{m+2}2\rceil$th column, so the queried diagonals are as far from each other as possible. This way, we will have 2 queried cells in each row, and the rest of the $m-2$ cells in the row are divided into 2 or 3 groups, where the largest group's size is $\lceil\frac{m-2}2\rceil$. As $m\le6$, $\lceil\frac{m-2}2\rceil\le2$, so even if we have to check all the $\lceil\frac{m-2}2\rceil$ cells in each of the $m$ rows, we don't exceed the limitation of $4\times m$ questions.

Please notice that

the restriction for the columns wasn't even utilised, and that the strategy wasn't really adaptive: which values to ask from the oracle wasn't depending on the previous answer for the first $2\times m$ cells at all. I have the intuition, that in a typical case the monotonity criteria coming from the columns gives another factor of $\frac12$ on the size of the groups, so $m\le10$ can be solved.

$\endgroup$
1
$\begingroup$

The General Answer

First of all, we need to consider odd dimension grids and even dimension grids separately. Because their solution is close but separate.

Let's start with odd dimension one: 5x5

enter image description here

This is

The first numbers you need to ask for, because you would know the biggest and the smallest value in the grid. Even cells are easier in my option.

Then

you may even be able to eliminate some cells which would not be having the number you are looking for. But if you are unlucky, you may not if our number is in between all those values. For example, if $A=100$, $B=1$, $C=12$ and $D=50$, and the number you are looking for $27$, you will not able to eliminate any cell for this moment.

Let's guess

other corner values in the inner square

shown below:

enter image description here

This is better guess because you will able to eliminate some cells for sure now because

If our number is in between E-F you will able to eliminate first and last cells on the second column, if our number is greater/smaller than F and smaller/greater than E, we can eliminate two cells. So whatever our number is, we can eliminate two cells from the grid. For example let's say our number is $27$, $E$ is 20 and $F$ is $10$, then you can eliminate two cells etc. Likewise, we can eliminate two more cells from the second row which is not common with the column, (I will call it E-H column) Likewise on the H-G column and F-G row, we can eliminate another 4 cells whatever number we have!

So ,

enter image description here

So for example, one of the worst case is

enter image description here

Note that the red cells are the cells where our number cannot be there.

So only asking 4 more cells shown below, will eliminate another 4 cells with

the same logic above, asking for I,K,L,J will guarantee that 2 white cells left:

enter image description here

So

in total for 5x5, 15 cell asking guarantee to find or not your number exists. This is optimal solution for 5x5! Even if you asked for every white cells left, it would be sufficient for $4m$,

Here is why:

In general You need to ask diagonal values first, then eliminate all cells when possible, then ask for cells not to next to each other in a row or column, and eliminate accordingly. When the dimension increases, elimination number of cell you can eliminate is getting bigger, for example for 5x5, you can eliminate $8$ cells in this process, but for 7x7, you can eliminate $8+16$ cells in total.

In general, you can eliminate

$4\left (\frac{m-1}{2}-1 \right )\left (\frac{m-1}{2}\right )=m^2-4m+3$

so you asked for

$2(m-1)$ cells,

and

eliminated $m^2-4m+3$ out of $m^2$ cells

and white cell count becomes

$m^2-(m^2-4m+3)-(2m-2)=2m-1$

so we asked for

$2m-2$ and $2m-1$ cells left. If we ask all cells one by one, $4m-3$ cells would be asked which is smaller than $4m$.

As shown below (11x11):

enter image description here

And for the rest of while cells,

$2(m-1)$ diagonal cell asking + even you dont have to, asking the rest of while cells which is $2m-1$ is sufficient to have smaller than $4m$. For your information, asking all white cells left is not optimal, but as I said it is sufficient to have less than $4m$.

$\endgroup$
  • $\begingroup$ How does this work when the original uncovered corners are: top left 1, top right 21, bottom left 25, bottom right 11? Supposing we are looking for value 12, no cells can be excluded directly in this case I think. $\endgroup$ – elias Aug 7 '18 at 14:03
  • $\begingroup$ The problem does not state that the numbers are integers, so how about this: 1,13,19,20,21;22,21.5,20.5,19.5,18;23,22.5,21.6,18.6,17;24,23.5,22.6,17.6,16;25,24.5,24.4,12,11 $\endgroup$ – elias Aug 7 '18 at 14:13
  • $\begingroup$ I'm not sure I get your notation right. Shouldn't the top-row second cell be black on the picture you posted in your comment? $\endgroup$ – elias Aug 7 '18 at 14:25
  • 1
    $\begingroup$ @Oray It's not very hard to change the numbers to make it work again. Pretend the example was 105, 205, 104, 204, 103, 203, 102, 202, 101, 201, (middle here), 99, 89, 98, 88, 97, 87, 96, 86, 95, 85 instead. Almost exactly the same, except with the top half reversed. $\endgroup$ – Persona Aug 8 '18 at 16:04
  • 2
    $\begingroup$ @Oray Have a 17x17 grid for free, too. Remember, worst case, binary searches always put the number you're looking for on the bigger half! $\endgroup$ – Persona Aug 9 '18 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.