Before contest

Codeforces Round 955 (Div. 2, with prizes from NEAR!)

12:24:02

Register now »

Codeforces Round 955 (Div. 2, with prizes from NEAR!)

12:24:02

Register now »

*has extra registration

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

1 | tourist | 3845 |

2 | jiangly | 3707 |

3 | Benq | 3630 |

4 | orzdevinwang | 3573 |

5 | Geothermal | 3569 |

5 | cnnfls_csy | 3569 |

7 | jqdai0815 | 3532 |

8 | ecnerwala | 3501 |

9 | gyh20 | 3447 |

10 | Rebelz | 3409 |

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

1 | maomao90 | 171 |

2 | adamant | 163 |

3 | awoo | 162 |

4 | nor | 153 |

5 | maroonrk | 152 |

6 | -is-this-fft- | 151 |

7 | TheScrasse | 150 |

8 | atcoder_official | 145 |

8 | Petr | 145 |

10 | pajenegod | 144 |

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/25/2024 05:11:00 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Another great blog by nor sir!

norz

orz sir!!

Read the last line of this blog (thank me later)https://codeforces.com/blog/entry/92248

You briefly mentioned this, but partition_point with iota_view is kind of nice to use now:

Yeah, that's correct. I have used it in a past submission once, and it was one of the reasons why I wanted to write this blog: https://codeforces.com/contest/1550/submission/132417058

starred, will read it later , too lazy to read such long blog right now.Thanks for such helpful blog.

Another top contributor in making. Orz.

Why not mid = (l + r) / 2? It is easier and faster to write in all [l, r) algorithms(segment tree, binary search).

may overflow ?

I have never seen a task, where (l+r)/2 is a problem. But when I need to operate with numbers > 4*10^18, I use __int128

That's correct. I use

`(l + r) / 2`

in algorithms where these are just indices. However, while templating code (for instance in dynamic segtree), I prefer using stuff like`std::midpoint`

and so on, since it makes it less error-prone. Just a matter of personal preference I guess.Another usecase of

`std::midpoint`

is that if you're templating some code and use`auto`

rather than a template, then if you accidentally have the endpoints of the range of different types, then the call to`std::midpoint`

fails to compile, which is also nice imo.main reason we that because that is buggy for negative integers due to rounding off error, hence you use that see the topcoder article on binary search.

also for another version we have to use mid = l + (r — l + 1) / 2.

but it will work for while(l <= r) version.

i guess best version is while(l + 1 < r).

True. The corresponding bug can be seen in the case where $$$[l, r) = [-1, 0)$$$, and doing

`m = (l + r) / 2`

gives you $$$m = 0$$$, and this can lead to an infinite loop.As I mentioned in the blog, using the floor version rather than the ceil version (while thinking in terms of $$$[l, r - 1]$$$ rather than $$$[l, r)$$$), i.e.,

`m = (l + r - 1) / 2`

, will also work correctly for integer division, since it mimics the other ways (though the semantics of the choice of midpoint generally depend on the sign of the sum of $$$l, r$$$, and this just coincidentally works).Another point regarding overflow:

`r - l > 1`

as mentioned in the blog can be buggy at times if the distance between $$$r, l$$$ doesn't fit in that integer type. Using`l + 1 < r`

should be fine, if we also check for certain bounds on the inputs of the function call.`mid=l+r>>1`

is faster because`>>1`

is much faster than`/2`

, and it also saves a byte:)The way you explained inclusive and exclusive search is just one of its kind. I had my worst time understanding which implementation should be used for a particular problem. Even though, I am still biased towards one of them, this blog actually gives you good insights on when to prefer some implementation over the other.

Another way of looking at it is: everything in the range [l,ans) corresponds to true, and everything in the range [ans,r) corresponds to true.

nor is this a typo?

Thanks for pointing it out! Fixed.

Nvm

That's the implementation I use in this blog as well (you have a bug though, $$$R$$$ should be $$$n$$$ instead if your search space is $$$[0, n - 1]$$$). I think of it as bringing two borders together (the "already known values").

Yes, I missed that you have my implementation in the blog.

amazing. I was facing much trouble in implementing BS. But, sir you have explained clearly. Thanks a lot.

Hi nor. Thanks for this great blog! Can you/someone else explain this behaviour? Or is it passing due to weak test cases?

Probably because of weak tests. You should try to understand what invariant the binary search keeps at each iteration, because in any binary search problem, you exploit the invariant at the end to claim that the found index is the answer. Thinking about the invariant will also fix your indices.

Thanks, got it!

Great blog "Binary searching on the answer" problems stucked me twice recently... T.T https://atcoder.jp/contests/abc155/tasks/abc155_d https://codeforces.com/problemset/problem/1852/A