Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### jack07's blog

By jack07, history, 5 weeks ago, , • Whenever I've to face an interactive problem, I just change the question.
• i.e., I get scared because once I tried to solve Interactive Promblem and all time I got Idleness Limit Exceeded and after that day I ne'er solved any interactive question.
• But yesterday I found a nice problem which boosted my confidence over solving interactives.

So in this question my approch was :

1. Check for the answer between l and r.
2. Do it till we get answer from computer as "x";
• Now to identify what will be l and r,
• Firstly l= 1st bit 1 and all zero before and after that, r=next bit of l (MSB of l)+1 to be 1 and all zero. Increase 1 bit each time.

• (0, 1) then, (1, 10) then, (10, 100) and so on... (In binary representation).

• (0,1) then (1,2) then (2,4) and so on..(till 2^31)

• Now we do this to identify our answer lies between l+1 and r we get.

• This is because l will be smallest number with that MSB so we check for all powers of 2.

• We can get this in at most 31 queries.

Now,

• If we binary search between l+1 and r then we will find our answer within 30 queries.

• The binary search approch was like,

• let m=(l+r)/2;

• Ask for answer between l and m (Here we just need to print (? l m) and take input from computer).

• If answer is "x" then shift r to m, shift l to m otherwise.

Now,

• As we are dealing with interactive problem so we need to flush the output we give.

• For that use 'endl' after each cout instead of '\n'.

• That's all we need to change between a regular problem and interactive problem.

• We can also use fflush(stdout) but 'endl' does it.

It was a blessing in disguise.

So I just want to conclude that Interactive problems ain't that arduous to deal with.

Thank You and let me know if I'm wrong.  Comments (6)
 » Everything is difficult until we succeed. :)
•  » » Yes that's true.
 » 5 weeks ago, # | ← Rev. 2 →   I have that similar issue with number theory and maths questions. Any other topic, I can crack upto 2000, maybe even higher rating questions, but on this particular topics, I can barely solve 1600 rating questions. Still looking for my rescue problem lol.
•  » » I hope to crack upto 2000. 'Coz I can solve mostly till 1400.
•  » » » Keep Practising, I'm sure you'll get there.
•  » » » » Sure. Thanks.