Confidence Augmenter For Interactive Problems.

Правка en1, от jack07, 2020-06-02 13:03:38
  • 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. — The question link... [cut]
  • **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"; [cut]
  • Now to identify what will be l and r,
  • Use bitmask, like [cut] 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. [cut] 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. [cut] 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. [cut]
  • 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'. [cut]
  • It was a blessing in disguise.
  • So I just want to conclude that Interactive problems ain't that arduous to deal with. [cut] Thank You and let me know if I was wrong.
Теги #binary search, interactive problem, #math

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский jack07 2020-06-02 13:24:45 472 Tiny change: 'with. \n\n### Thank You ' -> 'with. \n\nThank You ' (published)
en3 Английский jack07 2020-06-02 13:06:20 28
en2 Английский jack07 2020-06-02 13:04:48 50
en1 Английский jack07 2020-06-02 13:03:38 1764 Initial revision (saved to drafts)