Task Author: Gordon Cormack (CAN)

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,
than the secret number can be determined with one additional guess.

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.
See below for a Pascal program.

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 = (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 = MOr 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.

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}≤N.
That is, it makes at most log_{2} N^{2} (rounded up) calls to **Guess**.
For N=500 (almost 2^{9}), this boils down to making at most 18 calls.

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).

A Pascal program is given below.

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} 3*N = 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 distinghuish two cases for the location of this interval
with respect to the initial interval:

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

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

whereaaaabbbbbbdddddddddd

`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:

This guess compares to M = (G+R)/2 = (P-2 + P+2aaaabbbbbbdddddddddd 1G P M R

*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

*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.

A C program solving Subtask 4 can be found here.

const Colder = -1; Same = 0; Hotter = +1; type TResult = Colder .. Hotter; function HC(N: Longint): Longint; { returns secret number of Jill } var r: TResult; { result of Guess } G: Longint; { argument for Guess } begin if N = 1 then begin HC := N ; Exit end { if } { N >= 2 } ; G := 1 ; r := Guess(G) { ignored } ; repeat { numbers >= G are remaining candidates; G < N } G := G + 1 ; r := Guess(G) { compares to G - 0.5; r <> Same } until (r = Colder) or (G = N) ; case r of Colder: HC := G - 1; Hotter: HC := G; end { case r } end;

const Colder = -1; Same = 0; Hotter = +1; type TResult = Colder .. Hotter; function HC(N: Longint): Longint; { returns secret number of Jill } var r: TResult; { result of Guess } a, b: Longint; { [a .. b] is interval of remaining candidates } begin if N = 1 then begin HC := N ; Exit end { if } { N >= 2 } ; a := 1 ; b := N { invariant: 1 <= a <= b <= N } ; while a <> b do begin r := Guess(a) { ignored } ; r := Guess(b) { compares to (a+b)/2 } ; case r of Colder: b := (a + b - 1) div 2; { largest integer < (a+b)/2 } Same: begin a := (a + b) div 2 ; b := a end; Hotter: a := (a + b + 1) div 2; { smallest integer > (a+b)/2 } end { case r } end { while } { a = b } ; HC := a end;