Tell me more ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.
up vote 5 down vote favorite

I'll participate in IOI 2011 this year, and I'm solving past IOI problems in order to get properly prepared. This problem is quite difficult. A binary search which uses two guesses to provide a higher/lower comparison to mid would only work for subtasks 1, 2. Please help me in solving the full problem! Any idea which would help is welcome! My current algorithm looks something like:

int lo = 1, hi = N;
while( lo != hi ) {
guess( lo );
temp = guess( hi );
if( temp == HOTTER )
    lo = mid;
else if( temp == COLDER )
    hi = mid;
else
    we've found the answer, it's just mid!
}

Thanks in advance!

share|improve this question
1  
Do you have a more specific question? You're now asking for others to read the entire problem description, and (perhaps?) provide a complete solution. – Bart Kiers Jul 1 '11 at 18:42
Well, yes, I need a suggestion to reduce the binary search space in less than two guesses. I'll add that to my question. But also, if a better solution exists, sure! – Abody97 Jul 1 '11 at 18:44
4  
Also, you've already asked an IOI question earlier today. You should try harder to solve these on your own as it would be much better practice than asking someone else to do it for you. – tskuzzy Jul 1 '11 at 19:25
1  
My current algorithm looks like this: lo = 1, hi = N while( lo != hi ) { guess( lo ); temp = guess( hi ); if( temp == HOTTER ) lo = mid; else if( temp == COLDER ) hi = mid; else ( we've found the answer, it's just mid ) } – Abody97 Jul 1 '11 at 19:30
2  
o.O 14 year old in the IOI. (Although I can't really speak. I'm <14 :P in the IOI as well) Anyway: 1) You should really like... solve it yourself. If you need to ask to solve it, it won't really help you. You'd be better off solving other problems and waiting for the day that you're good enough and find the solution. 2) Have a look at Median Strength (another past IOI problem). <spoiler> It's similar and can actually be solved with what tskuzzy has shown below. </spoiler> 3) What country are you from/representing at IOI? – quasiverse Jul 2 '11 at 2:30
show 4 more comments

migrated from stackoverflow.com Jul 3 '11 at 12:54

closed as off topic by dmckee♦ Jul 4 '11 at 1:03

Questions on Programming Puzzles & Code Golf Stack Exchange are expected to relate to programming puzzle or code golf within the scope defined in the FAQ. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about closed questions here.

1 Answer

up vote 2 down vote

I'm gonna change the problem slightly to make it easier to describe. I'm gonna describe a solution to finding a real number R in the interval [0,1].

Try the following (I'm not 100% this works)

Guess 1/3
Guess 2/3

If it's hotter, then you know that R is in (0.5,1]
If it's colder, then you know that R is in [0,0.5)
If the same, then R = 0.5 and you're done

Let's suppose it's "colder" so R is in [0,0.5)
Guess 1/6

If hotter, then R is in [0,0.25)
   colder, then R is in (0.25,0.5)

etc.
share|improve this answer
1  
Well, the actual question is: how many guesses are you doing? Isn't the same number of guesses that my algorithm makes? – Abody97 Jul 1 '11 at 20:14
I believe in my algorithm every guess halves the search space as opposed to yours in which the search space is halved every two guesses. – tskuzzy Jul 1 '11 at 21:34
Take an example: 1 2 3 4 5 6 7 8 9 Where the "hidden" number is 8 Your algorithm fist guesses 3, then 6, which is hotter, so you halve the search to get: 4 5 6 7 8 9 Then you are going to guess 6? If so, you'll get same, which is useless. – Abody97 Jul 2 '11 at 7:54
No, after guessing 6, you're left with 5,6,7,8,9. Then you guess 8 which is hotter and you're left with 8,9. Then guess 9 -> colder -> answer = 8 :) – tskuzzy Jul 2 '11 at 14:41
Well, in general, you guess the 2 / 3, supposing we already guessed 1 / 3 before halving? – Abody97 Jul 2 '11 at 20:22
show 2 more comments

Not the answer you're looking for? Browse other questions tagged or ask your own question.