wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Hot or cold
        
(Message started by: Skandh on Sep 16^th, 2011, 8:47am)

Title: Hot or cold
Post by Skandh on Sep 16^th, 2011, 8:47am

Problem Definition goes like this :

Hot or cold. Your goal is the guess a secret integer between 1 and N. You repeatedly guess integers between 1 and N. After each guess you learn if it equals the secret integer (and the game stops); otherwise (starting with the second guess), you learn if the guess is hotter (closer to) or colder (farther from) the secret number than your previous guess. Design an algorithm that finds the secret number in ~ 2 lg N guesses. Then, design an algorithm that finds the secret number in ~ 1 lg N guesses.

I am able to solve first part using Binary Search, but not able to reduce number of guesses to ~ 1 lg N.

Please provide some pointers to proceed with it.

Title: Re: Hot or cold
Post by towr on Sep 16^th, 2011, 9:35am

Just doing binary search seems to work. Start with 1, if N is hotter, then the number lies in (1+N)/2 to N, then if (1+N)/2 is colder, it lies in (N+(1+N))/2 to N, etc. You reduce the search space by a factor of two each step.

Title: Re: Hot or cold
Post by Skandh on Sep 16^th, 2011, 10:18am

on 09/16/11 at 09:35:10, towr wrote:

That's correct. But hotter and colder are defined with respect of ( as far as I see it ) older guesses rather than any other number.

if the guess is hotter (closer to) or colder (farther from) the secret number than your previous guess

I'll just elaborate with an example for first part of the question :

Say N=32.
Secret Number = 21

Take mid = 16

First Guess = 8
Second Guess = 24

Since 24 is hotter than 8 so we select interval [17,32]

and so on.

Please correct me if I am wrong.

Title: Re: Hot or cold
Post by towr on Sep 16^th, 2011, 10:28am

I'd expect hotter or colder would be with respect to the last guess. So you pick the new number at the opposite end of the range to divide it in two.
So start at 1, then 32, then 16, then 24, then 20, then 22, then 21

Title: Re: Hot or cold
Post by Skandh on Sep 16^th, 2011, 10:35am

on 09/16/11 at 10:28:04, towr wrote:

So using this , in worst case, we'll have ~ 2 lg N guesses.

Now how can we decrease number of guesses to ~ 1 lg N?

I just saw hint on book website to decrease number of guesses to ~ 1 lg N, but still not sure how it'll help.

Hint : For the second part, first design an algorithm that solves the problem in ~1 lg N guesses assuming you are permitted to guess integers in the range -N to 2N.

Title: Re: Hot or cold
Post by towr on Sep 16^th, 2011, 12:48pm

I see now I was just plain wrong in my previous posts.

You want to use the middle between the last point and the next one to have the value you'd use normally for binary search, but to do that you have to pick them outside the range 1-N.
See the attachment for a quick example. Blue is the value you're looking for. The green line shows is your search space. 1,2,3,4,5,6 number the order in which the ends are picked to reduce the search space by halve each step.