jeroenodb's blog

By jeroenodb, 23 months ago, In English

If you're looking for some binary search practice, this blog might be for you. I have compiled a list (I've heard lists are very popular on CodeForces) of some problems I really liked. The only criteria I used is that the solution for the problem has to be vaguely related to binary search. And I also tried to have some variety in the problems I chose, so they are not all the same type of application of binary search.

Here are 12 problems, in a roughly increasing order of difficulty, that are vaguely (or less vaguely) related to binary search:

  1. 1672E - notepad.exe
  2. Median of two sorted arrays Although the time limit doesn't enforce it, try to make a $$$O(log(n+m))$$$ solution.
  3. IOI 2013 Cave or if you prefer the Codeforces archive: IOI 2013 Cave
  4. IOI 2020 routers
  5. IX'th Problem from NWERC 2021
  6. Worm Worries BOI 2018
  7. IOI 2015 Scales. Codeforces archive link: IOI 2015 Scales
  8. Peer Streaming Spotify 2011
  9. 1028G - Guess the number
  10. Secret Sequence Swedish Coding Cup 2017
  11. IOI 2017 Prize. Codeforces archive link: IOI 2017 Prize
  12. 1483E - Vabank

It turns out the coolest uses (or variations) of binary search I know appeared in interactive problems, who would have guessed :)

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

»
8 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Do you have curated problems like that in the other topics? if yes , could you please share it