Thursday, August 26, 2010

IOI: A Medium Problem

Here is another, medium-level problem from the IOI. (Parental advisory: this is not quite as easy as it may sound!)


I think of a number between 1 and N. You want to guess the secret number by asking repeatedly about values in 1 to N. After your second guess, I will always reply "hotter" or "colder", indicating whether your recent guess was closer or farther from the secret compared to the previous one.

You have lg N + O(1) questions.

***

The solution to the first problem I mentioned can be found in the comments. Bill Hesse solved the open question that I had posed. He has a neat example showing that the space should be N1.5log23 bits, up to lower order terms. It is very nice to know the answer.

A very elegant solution to the second problem was posted in the comments by a user named Radu (do you want to disclose your last name?). Indeed, this is simpler than the one I had. However, the one I had worked even when the numbers in the array were arbitrary (i.e. you could not afford to sort them in linear time). I plan to post it soon if commenters don't find it.

22 comments:

x10000year said...

Quite easy. First ask 1 and N, so you know which half the secret number lies in. Then repeat the above process, each time cutting the possible range into half.

AB said...

x10000: that sounds like it takes 2 lg N, which is not allowed.

What is the response if the secret number is exactly half way between the previous two guesses? Do you say "equal" and I win in that case?

x10000year said...

AB:
Only the first turn needs two questions. Every successive turn needs only one question.

x10000year said...

Sorry, I'm wrong. I'm not able to delete my comments.

x10000year said...

Suppose we know that the secret number lies in [1,N/2] (with one or two additional questions)

Because we need to find out the secret number in at most lg_2(N) questions, each question must cut down the possible range into half in average.

So first assume the secret number is 1. The last question should guess 1, which cuts down [1,2] into half. The second last question should guess 2, which cuts down [1,4] into half. The third last question should guess 3, and the 4th 6, the 5th 11, ...

The the kth last question should guess f(k), where f(1)=1 and f(k)+f(k+1)-1=2^k. Each question can cut down the possible range into half. We can first guess f(k) for the first k that f(k)>N/2.

When the secret number is not 1 (but less than N/2), we still choose the next guess value that can cut down the possible range into half. The value being asked will lie in the range [1,N].

Anonymous said...

Mihai, shouldn't it be hotter/colder/same? Otherwise I don't think you can do it in log (n) + O(1).

Anthony said...

In this game, it seems as if getting the answer "colder" is bad since the next move will not bring any new information (it will necessarily hotter...).

Therefore, I think the strategy should be designed to have a bias in favor of hotter (which is not the case for usual dichotomy techniques).

Anonymous said...

If we can ask with values outside 1...N then it is easy.

Mihai said...

Yes, it is hotter-colder-same. When you get "same" you have guessed the answer.

No, you cannot ask for numbers outside 1..N

As I said, this is not as easy as it may sound. But I like the problem since it sounds very canonical :)

Adam Smith said...

Mihai,

This is a cute problem and would make a good homework problem for an algorithms course (although it might require hints depending on the level of the students).

Is there a repository of past IOI problems, ideally tagged or sorted by topic and difficulty? It is a pain to come with fresh problems year after year, and a bit of reformulation is usually sufficient to stop students from finding solutions online.

Also, it might be a fun resource with which students could test themselves.

Mihai said...

Adam, the list of problems is in principle available here: http://ioinformatics.org/history.shtml

Too bad these are the official task descriptions, which contain a lot of fluff. I would love a list with short descriptions in mathematical notation.

Travis said...

Anonymous' comment that if you can guess numbers outside of 1...N then the problem is easy can be extended to a solution. In particular if you know the secret number is in the interval [l,u] then it suffices to be able to ask numbers in the interval [l-(u-l), u+(u-l)]. With this possible range of guesses it is possible to find the secret number in only lg(u-l) + O(1) questions (starting with guessing l and u and for further guesses, guessing the smallest number outside of the [l,u] interval in order to cut the remaining interval in half).

Reducing the original problem to this simpler form is fairly easy. Simply guess initially N and 0. Assume wlog that the secret number is in [0, N/2]. Set k_0 = N/2.

Given an interval [0, k_i] we guess k_i/2 if our previous guess was 0 and 0 if our previous guess was k_i. If we learn that the secret is in the interval [k_i/4, k_i] we then almost have an instance of the simpler version of this problem which we can solve. Using O(1) guesses though we can easily turn this into an instance of the simpler problem.

Otherwise the solution is in [0,k_i/2] in which case we set k_{i+1}=k_i/2 and recurse.

Each step cuts the interval we have to consider in half and we use at most lg(n) + O(1) guesses

x10000year said...

Travis:

I don't think your solution can work when the secret number is 1. Your approach may need 2lgN questions.

Anonymous said...

Given an interval [0, k_i] we guess k_i/2 if our previous guess was 0 and 0 if our previous guess was k_i

Should you guess k_i/4 instead of k_i/2 to ensure the interval size goes down by a factor of 4 after every two guesses?

Travis said...

There was a typo in my previous comment. Since 0 is outside of 1,...,N replace each occurence of 0 in my previous comment with 1

I don't think your solution can work when the secret number is 1. Your approach may need 2lgN questions.

Consider the case where the secret number is 2 (2 instead of 1 as you mention because of my off by one error above). The first guess is N followed by 1. Since the secret number is 2, we learn that it is in the lower interval [1, N/2]. The next guess we make is N/4. We then learn the secret number is in [1, N/4]. Then we guess 1 and learn that the secret number is in [1, N/8] and so on. Each guess cuts the interval in half so only lg(n)+O(1) guess are required when the secret number is 2.

Given an interval [0, k_i] we guess k_i/2 if our previous guess was 0 and 0 if our previous guess was k_i

As long as the secret number is in the lower interval, we cut our possible choices in half. If we discover it is in the upper interval than we simply use O(1) guess to reduce it to an appropriate size to get an instance of the "simpler problem". So in each guess cuts in the interval we have to consider in half except for possibly one of the guesses we make.

xreborner said...
This comment has been removed by the author.
Anonymous said...

@Travis and what happens when the secret number is N-1 ?

Travis said...

@Travis and what happens when the secret number is N-1 ?

The situation where the secret number is in [N/2, N] can be handled in the same manner as when the secret number is in [1, N/2]. Instead of considering intervals of the form [0, k_i] we have intervals of the form [k_i, N].

Anonymous said...

@Travis for N=100 and X=2 the following guesses are made according to your algorithm:
[1] 100
[2] 1 Hotter
[3] 50 Colder
[4] 1 Hotter
[5] 25 Colder
[6] 1 Hotter
[7] 12 Colder
[8] 1 Hotter
[9] 6 Colder
[10] 1 Hotter
[11] 3 Same
For each Hotter there is a Colder so in this case you require 2lgN guesses. There may be a lot of "Colder" answers and their count can go up to lgN.

Every algorithm I tried was for N and 2 and this case is really awful.

Anonymous said...

Let's say the current interval [a,b] has been reduced after a Colder answer to guess c and that a<b<c. Then we don't guess Max(1, a+b-c) as @Travis does (i.e. lower bound or outside the interval) but we choose a+(b-a)/4 (i.e. inside the interval while splitting in 4). This way we have more reductions over the other algorithm.

Splitting in 4 works better than in 2. Meaning that starting with N/4 instead of N,1,N/2 works better (one guess less).

These optimizations combined with an "aggressive" interval reduction gives better upper bounds for a given N than the other algorithm.

Samuel said...

Here is my suggestion (not checked thoroughly):

Starting from k=0, then 1, 2... test value N/2^k.
Sto as soon as you get a "colder" at k=x.
Then there is enough room to simulate a normal binary search. Complexity estimate = lg(N/2^x)+x+O(1) = lg(N) + O(1).

Samuel said...

Sto = Stop, and my tentative solution appears identical to Travis' one. I might add that if the first answer (at k=1) is "colder" then we should do a u-turn (going left) and continue as if the answer was "hotter".