This problem is an interesting variant of the well-known guessing game Higher-Lower, also featured in the demonstration task Guess.

Higher-Lower is efficiently solved by the, also well-known, Binary Search algorithm. Binary Search maintains an interval of still possible numbers (candidates). Initially, this interval includes all numbers in the range. By comparing to the middle candidate, the interval can be halved by a single guess. Thus, the secret number can be determined in a logarithmic (to base ~2~) number of guesses. Or, to put it differently, if the range of allowed numbers is doubled, then the secret number can be determined with one additional guess.

Subtask 1

Doing a Linear Search, that is, successively calling Guess(~i~) for ~i~ from ~1~ to ~N~, yields a solution requiring ~N~ calls to Guess, in the worst case. This solves Subtask 1.

Analysis

To get a better understanding of the Hotter-Colder problem, it helps to formalize the rules of this game.

Let ~J~ be Jill's number, and let ~P~ be the most recent guess, that is, Guess(~P~) was called last. In that situation, Guess(~G~) will return:

HOTTER if abs(G - J) < abs(P - J)
COLDER if abs(G - J) > abs(P - J)
SAME   if abs(G - J) = abs(P - J)

Or in a single formula: sign(abs(P - J) - abs(G - J)). Letting ~M = \frac{P+G}{2}~, this can be rephrased as:

if P <= G then
  HOTTER if J > M
  COLDER if J < M
  SAME   if J = M
else
  HOTTER if J < M
  COLDER if J > M
  SAME   if J = M

Or in a single formula: sign(G - P) * sign(J - M).

Thus, we see that each Guess(~G~) effectively provides a high-low comparison to the midpoint ~M~. In fact, sign(G - P) * Guess(G) = sign(J - M) offers a genuine high-low comparison.

Unfortunately, due to the range restriction on ~G~, we cannot make the midpoint ~M~ go wherever we want. So, a straightforward Binary Search is not going to work.

Subtask 2

Ignoring the results of all odd calls to Guess, we can extract one bit of information out of every successive pair of odd-numbered and next even-numbered call to Guess. This yields a solution that calls Guess at most ~W~ times, where ~W~ is the largest integer such that ~2^{W/2} \le N~. That is, it makes at most ~2 \lceil \log_2 N \rceil~ calls to Guess. For ~N = 500~ (almost ~2^9~), this boils down to making at most ~18~ calls.

Subtask 3

By exploiting the fact that we actually do a high/low/equal comparison instead of a pure high/low (binary) comparison, we can gain almost one extra bit of information (taken over all guesses).

Explanation: a complete binary tree with ~2^k~ leaves has ~2^k-1~ internal nodes. So, the same number of high/low/equal guesses can reach twice the number of nodes minus one (compared to using just binary high/low guesses).

Subtask 4

The preceding approaches obviously throw away (ignore) valuable information. However, using this information requires careful tuning of the guesses. It helps to do some small cases by hand.

• ~N = 3~ can obviously be done in ~2~ guesses, by straddling the middle, for example, Guess(~1~) followed by Guess(~3~) does a high/low/equal comparison to ~2~.

• ~N = 5~ can be done in ~3~, but this already needs some care, because it does not work to set this up so that the first two guesses compare to the middle number ~3~. When, after Guess(~1~) Guess(~5~), or Guess(~2~) Guess(~4~), the result of the second guess is colder, you won't be able to solve the remaining problem in a single guess.

  You need to start with Guess(~1~) Guess(~3~) (or symmetrically Guess(~5~) Guess(~3~)). If the result of the second guess is same, Jill's number is ~2~; if the result is colder, only candidate ~1~ remains and this must be Jill's number. If the result is hotter, candidates ~3~, ~4~, and ~5~ remain. Since ~3~ was the most recent guess, doing Guess(~5~) will compare to ~4~, and we are done.

In general, it turns out to be possible to determine Jill's number in no more than ~\log_2(3N) = \log_2 3 + \log_2 N~ calls of Guess.

We explain one such algorithm. Because of the nature of the guess (being a comparison), at any moment you have an interval of remaining candidate numbers. You can distinguish two cases for the location of this interval with respect to the initial interval:

1. either this interval of candidates contains ~1~ or ~N~ (is "against a wall");
2. or it contains neither ~1~ nor ~N~ (is "in the middle").

Furthermore, you know what the previous guess was, say ~P~.

If the interval of candidates is "in the middle", then you are home free (provided you are a bit careful), because now each guess can be made to reduce the interval sufficiently. In ~K~ more guesses, you can find Jill's number among ~2^{K+1}-1~ candidates. [Details suppressed (for the time being)]

If the interval of candidates is "against a wall", then you can always arrange it so that the interval is ~1~ through ~P~ (or symmetrically on the other side). With two extra steps, you can grow a solution that solves for ~P~ in ~K~ more guesses to one that solves for ~P+2^{K+2}~ in ~K+2~ more guesses.

The base cases are ~P=3, K=1~ and ~P=7, K=2~.

The construction works like this. Consider the interval:

aaaabbbbbbdddddddddd

where

• aaaa is the interval ~1~ through ~P~ (and we assume that if the most recent guess was at ~P~, then an additional ~K~ guesses can determine Jill's number in this interval);
• bbbbbb is of length ~2^{K+1}-2~;
• dddddddddd is of length ~2^{K+1}+2~;
• the most recent guess was ~R = P+2^{K+2}~.

Your next guess is ~G = P-2~:

aaaabbbbbbdddddddddd
1G P      M        R

This guess compares to ~M = \frac{G+R}{2} = \frac{P-2+P+2^{K+2}}{2} = P+2^{K+1}-2+1~, that is, the first element of the d-labeled subinterval. Do a case distinction on the result of this guess:

• Same: Jill's number is ~M~; done.
• Colder: the interval is reduced to ~M+1~ through ~R~; continue with a "middle game" on ddddddddd of length ~2^{K+1}+1~;
• Hotter: the interval is reduced to ~1~ through ~M-1~:

  aaaabbbbbb
  1G P      M

  Next, guess ~P~, which boils down to comparing to ~\frac{G+P}{2} = P-1~. Do a case distinction on the result:
  • Colder: "wall game" on interval ~1~ through ~P~ (aaaa), which we assumed can be solved in ~K~ more guesses;
  • Hotter: "middle game" on abbbbbb of length ~2^{K+1}-1~.