This problem is really three problems in one, for the cases of one, two and three dimensions. Most solutions work across any number of dimensions, but to get an optimal number of queries (for test groups 2, 4 and 6), the three cases required separate solutions.

1 dimension

We can first try something like a binary search. Let's say we have a grid of size $N\times 1\times 1$. We can reduce the problem to a smaller one as follows: ask for the value of the middle two points, say $H[N/2]$ and $H[N/2+1]$. If $H[N/2]\ge H[N/2+1]$, then we can reduce the problem to finding a local maximum of the first half of the array (including element $N/2$), otherwise to the second half.

However, this uses $40$ queries for $N=1000000$, while test group 2 requires at most $35$. Another approach, based on the idea of golden section search, gets to $35$ queries.

Say we want to find a local maximum in the interval $[a,b]$. If $a=b$, then we just return $a$. Otherwise, we might query two points $m,m+1$, say in the middle of the interval, and recursively find a local maximum in either $[a,m]$ or $[m+1,b]$, depending on which of $H[m],H[m+1]$ is bigger. But we don't need the queried points $m,m+1$ to be adjacent: suppose instead that we query two points $x,y$, $x<y$. Again, if $H[x]\ge H[y]$, we can recurse in $[a,y-1]$; otherwise we recurse in $[x+1,b]$. But when we recurse in $[a,y-1]$, we already have one queried point in the interval, $x$, so we just need to query one point in the next step. To see why this recursion will indeed produce a local maximum, note that the point you find in the end will be the best among all the queried points.

To find the right $x,y$ to start with, we use the golden ratio $\varphi =\frac{1+\sqrt{5}}{2}$, or rather its inverse $\frac{\sqrt{5}-1}{2}\approx 0.618$. If we let $x=0.618a+0.382b$ (rounded to the nearest integer), $y=0.382a+0.618b$ to start with, and recurse in $[a,y-1]$, then $x\approx 0.382a+0.618(y-1)$, so the points in the middle will always roughly form the same golden ratio.

This solution uses $29\approx {\log }_{\varphi }N$ queries, whereas binary search would use $40\approx 2{\log }_{2}N$.

2 dimensions

We can reuse some of the ideas of the binary search from the one-dimension case. Let us ask about the values of a line that cuts the rectangle in two. Consider the maximum of the values, and also query the two values to the left and right of this maximum (assuming the cut is vertical). If they are both less or equal to the maximum value, our point is a valid answer. Otherwise, we can recurse on a side where it increases. Intuitively, if we then continued walking to larger and larger values, we could never again cross the cutting line, because the value we walked to was larger than every value on it. There are some subtleties to this, where we have to make sure to recurse on the side that has the previously found maximal query value if that value is larger than the maximum value on the cutting line – otherwise, a local maximum that we found in a subrectangle may not be a local maximum of a full rectangle. Correctly implemented, though, this solves subtasks 3 and 4, assuming you alternate vertical and horizontal splits. It can also be generalized to 1 and 3 dimensions, solving subtasks 1 and 5.

3 dimensions

One naive idea is to query points at random, and then print the best one, i.e. the one with the highest humidity. Another naive idea is to start from a random point, query adjacent points, and move in the direction of increasing humidity until you find a local maximum.

Neither of these ideas work very well in the worst case, but they can be combined into a solution: First query $Q/2$ points at random. Then choose the best one, and move in the direction of increasing humidity until you arrive at a local maximum.

Why does this work? Suppose in the first stage you find a point among the $Q/12$ best points. Then as you move to better points, you will need at most $Q/12$ steps. For each step, you might need to query $6$ points (or $3$ on average if you do this cleverly), so you will need $Q/12\cdot 6=Q/2$ queries in the second stage, i.e. $Q$ queries in total. So we succeed if we find a point among the $Q/12$ best points.

The probability of not finding one of these points is at most:

$${\displaystyle {(1-\frac{Q}{12NMK})}^{Q/2}\approx \exp (-\frac{Q}{12NMK}\frac{Q}{2})=\exp (-\frac{Q^2}{24NMK})}$$

For group 6, this gives a probability of failure less than $1$ in $1800$. This solution will also solve groups 1, 3, and 5.

Fun facts about this problem

• The grader for this task was 900 lines long, and implemented 14 different strategies for (on-demand per query) test data generation. This included random test data, space-filling curves, spirals, random line segment paths with slopes leading up to them, and fun 1d functions like randomly rescaled $\sqrt{x}$ and sawtooth functions.
• We had vague plans on extending the task to 4d, but scrapped them. If anyone wants code for random space-filling curves in 4d, just ask.
• Apparently this problem has been fairly well studied by computer scientists, with regards to upper and lower bounds. See for instance:
  • https://arxiv.org/abs/quant-ph/0504085
  • https://epubs.siam.org/doi/pdf/10.1137/S0097539704447237