rm17's blog

How to identify Binary Search on Answer type problems
By rm17, history, 4 years ago, In English

I've been confused, whenever i see a question, that if i can apply binary search on answer to solve this, leading to WASTAGE OF TIME during contests. If there is any particular hint that gives away whether I can apply BAA or not.

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
4 years ago, hide # |
← Rev. 2  
Vote: I like it +3 Vote: I do not like it

To be able to binary search for an answer, you should know that:

If some value $$$x$$$ doesn't satisfy the requirements for an answer, then all values lower than $$$x$$$ (or greater than $$$x$$$, depending on the question) doesn't also satisfy the requirements.

AFAIK it's formally called a monotonic function. Definitely not a professional on CP but from what I've seen I can say that plenty of interactive questions or some "minimum number of operations that satisfy the requirements" involve binary search. As for Codeforces, the first three Div. 2 problems doesn't involve too many BS questions. Other than that, I can say that if there's an array that you can apply sliding window, you can combine these two techniques together, it's not uncommon.

→ Reply