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.

# | User | Rating |
---|---|---|

1 | tourist | 3810 |

2 | MiracleFaFa | 3604 |

3 | Radewoosh | 3549 |

4 | maroonrk | 3527 |

5 | Benq | 3514 |

6 | slime | 3511 |

7 | Um_nik | 3480 |

8 | greenheadstrange | 3430 |

9 | ksun48 | 3401 |

10 | ecnerwala | 3346 |

# | User | Contrib. |
---|---|---|

1 | YouKn0wWho | 207 |

2 | Monogon | 200 |

3 | Um_nik | 193 |

4 | awoo | 190 |

5 | -is-this-fft- | 185 |

6 | sus | 177 |

7 | Errichto | 174 |

8 | antontrygubO_o | 173 |

9 | maroonrk | 167 |

9 | SecondThread | 167 |

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.

↑

↓

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/28/2022 12:41:39 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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.

I also feel the same way. I in most problems notice the monotonicity but can't figure out how to make the check function ( if condition). And in most questions under the problemset under tag binary search I solve without using it. Please can some share their thoughts and give some advice. And also if possible please share some beginner friendly pure bs problems