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.
![[home]](http://people.csail.mit.edu/mip/images/home.gif){kind=small}
22 comments:
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.
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?
AB:
Only the first turn needs two questions. Every successive turn needs only one question.
Sorry, I'm wrong. I'm not able to delete my comments.
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].
Mihai, shouldn't it be hotter/colder/same? Otherwise I don't think you can do it in log (n) + O(1).
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).
If we can ask with values outside 1...N then it is easy.
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 :)
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.
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.
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
Travis:
I don't think your solution can work when the secret number is 1. Your approach may need 2lgN questions.
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?
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.
@Travis and what happens when the secret number is N-1 ?
@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].
@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.
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.
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).
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".
Post a Comment