Jack and Jill play a game called Hotter, Colder. Jill has a number between 1 and N, and Jack makes repeated attempts to guess it.
Each of Jack's guesses is a number between 1 and N. In response to each guess, Jill answers hotter, colder or same. For Jack's first guess, Jill answers same. For the remaining guesses Jill answers:
hotter if this guess is closer to Jill's number than his previous guess colder if this guess is farther from Jill's number than his previous guess same if this guess is neither closer to nor further from Jill's number than his previous guess. You are to implement a procedure HC(N) that plays Jack's role. This implementation may repeatedly call Guess(G), with G a number between 1 and N. Guess(G) will return 1 to indicate hotter, -1 to indicate colder or 0 to indicate same. HC(N) must return Jill's number. Subtask 1 [25 points]
HC(N) must call Guess(G) at most 500 times. There will be at most 125 250 calls to HC(N), with N between 1 and 500.
Subtask 2 [25 points]
HC(N) must call Guess(G) at most 18 times. There will be at most 125 250 calls to HC(N) with N between 1 and 500.
Subtask 3 [25 points]
HC(N) must call Guess(G) at most 16 times. There will be at most 125 250 calls to HC(N) with N between 1 and 500.
Subtask 4 [up to 25 points]
Let W be the largest integer, such that 2W≤3N. For this subtask your solution will score: 0 points, if HC(N) calls Guess(G) 2W times or more, 25α points, where α is the largest real number, such that 0<α<1 and HC(N) calls Guess(G) at most 2W-αW times, 25 points, if HC(N) calls Guess(G) at most W times. There will be at most 1 000 000 calls to HC(N) with N between 1 and 500 000 000
I tried binary search for this. My code is,
int l=1,r=N;
while(l!=r){
Guess(l);
int a = Guess(r);
if(a==-1)
r = (l+r-1)/2;
else if(a==1)//close to l
l = (l+r+1)/2;
else return (l+r)/2;
}
return l;
This leads to a solution with $$$2*log(n)$$$ Guesses. (18 for 500) For subtask 3 I need a solution that finds the number in $$$<=16$$$ guesses. I've tried google but solutions seems a lot complex for me. I found subtask wise explanations here. I still couldn't understand it. Can someone please guide me to a more efficient solutions. Any help is appreciated. Thank you.
