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.
№ | Пользователь | Рейтинг |
---|---|---|
1 | ecnerwala | 3649 |
2 | Benq | 3581 |
3 | orzdevinwang | 3570 |
4 | Geothermal | 3569 |
4 | cnnfls_csy | 3569 |
6 | tourist | 3565 |
7 | maroonrk | 3531 |
8 | Radewoosh | 3521 |
9 | Um_nik | 3482 |
10 | jiangly | 3468 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
3 | adamant | 161 |
4 | TheScrasse | 159 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 152 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
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.
Название |
---|
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.