Help at an IOI problem!

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!

optimization

Chris

Posted 2011-07-01T18:37:47.237

Reputation: 193

1Do you have a more specific question? You're now asking for others to read the entire problem description, and (perhaps?) provide a complete solution. – None – 2011-07-01T18:42:27.110

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! – None – 2011-07-01T18:44:20.183

Firstly, before answering the question (if it remains open): congrats, and good luck for IOI. If you're really 14 years old as your profile says, double congrats! :-) – None – 2011-07-01T18:45:22.483

Can you clearly specify your current algorithm? This problem should involve some kind of binary-search-like so it would be helpful to know what you've tried. – tskuzzy – 2011-07-01T19:23:06.027

4Also, 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 – 2011-07-01T19:25:17.210

1My 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 ) } – None – 2011-07-01T19:30:53.170

2o.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? – None – 2011-07-02T02:30:03.227

I'm from Syria. And thanks for the advice, I'll checkout the problem ASAP :D – None – 2011-07-02T20:24:20.787

1Well, the actual question is: how many guesses are you doing? Isn't the same number of guesses that my algorithm makes? – None – 2011-07-01T20:14:03.000

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 – 2011-07-01T21:34:03.563

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. – None – 2011-07-02T07:54:32.813

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 – 2011-07-02T14:41:47.157

Well, in general, you guess the 2 / 3, supposing we already guessed 1 / 3 before halving? – None – 2011-07-02T20:22:05.590

Sorta. So you have an interval of possible solutions, call it [a,b]. And suppose you made a guess at x which lies in [a,b]. Your next guess would then be at a point y in that interval such that |x-(a+b)/2| = |y-(a+b)/2|. So think of it as reflecting x across the center of the interval. This is what allows you to halve the solution space. In my solution, I just chose the first point to be 1/3 arbitrarily. This is probably not optimal, but I hope I got the general idea across. – tskuzzy – 2011-07-02T21:47:34.947

Yes, thanks a lot! I get your idea. Thanks for the help and advice :D – None – 2011-07-03T08:13:08.450

Help at an IOI problem!

Answers