- 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:
- Check for the answer between l and r.
- Do it till we get answer from computer as "x";
- Now to identify what will be l and r,
- Use bitmask, like
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.
This will lead to check answer between powers of 2. - (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; - If answer is "x" then shift r=m, l=m otherwise; - Hence, answer is l+1.
- 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'.
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 was wrong.
