In the last Div.4 round, Problem 1985F - Final Boss witnessed numerous hacks, particularly targeting binary search solutions due to unexpected overflow in extreme cases.

A common challenge is determining the appropriate `high-value`

for binary search: choosing it too high (e.g., `1e18`

) risks overflow, while choosing it too low (e.g., `1e9`

) may lead to incorrect answers. Finding the perfect static `high-value`

for all cases can be tricky.

Here are two common fixes:

- Use a Very High Value and Handle Overflow with
`__int128`

(This approach can be complex and inefficient). - Select a Suitable "High-Value" through Trial and Error (Not an ideal solution).

### A More Sustainable Solution

As we know, binary search operates on a monotonic sequence such as `[0, 0, 0, ..., 0, 1, ..., 1, 1, 1, 1]`

. Our objective is to find the last 0 or the first 1 in this sequence. If we successfully set the `lo`

to any `0`

zero and `hi`

to any `1`

, our binary search will work perfectly. Now instead of relying on a static `high-value`

for all cases, we can dynamically determine the minimum `high-value`

necessary. This method involves starting with a low value and increasing it logarithmically until we find a suitable `high-value`

. This ensures that our binary search operates within a safe range. Here's how you can implement this:

```
long long lo = 0, hi = 1;
while(!check(hi)) hi *= 2; // Check returns either 0 or 1 based on hi.
```

At the end of the loop, `hi`

will point to a potential minimum `high-value`

. After that, you can write your regular code. You can check my solution to understand the technique better.

**My Solution**

Note: I learn this technique from fahimcp495. Forgive me for any mistake.

I hope this technique will be helpful for those who don't know about this technique. Happy coding!

Or one can simply put a

`break`

statement when the sum reaches beyond the desired answer (Specifically for yesterday's problem F)That's true, but this method is a general approach for most binary search problems. You don't need to consider anything else.

Yes that is a good thing it saved me from getting hacked and overflow.

could you elaborate a bit please?

Actually the author missed to keep a cap on the sum of values of attacks in last div 4 F ,so lot of hacks happened because in the check function of binary search, as it was calculating the sum of all attacks (it overflowed),so we could break the loop to sum up attakcs whenever the sum becomes greater than health .

Since you are talking about overflow issues, it is recommended to use

`mid = lo + (hi-lo)/2`

, as`lo + hi`

can exceed the`int`

or`long long int`

range, but`hi-lo`

is guaranteed to stay in the range :)Using

`mid = lo + (hi-lo)/2`

is good. I think using`mid = (lo + hi) / 2`

has no such overflow issue. Generally, the answer doesn't exceed`1e18`

. So, in the worst case when`hi = 1e18`

and`lo = 1e18`

and`hi+lo = 2e18`

, which can easily fit in`long long`

range. In this method`hi`

will never reach`1e18`

unless the answer is in`1e18`

range. If the answer exceeds`long long`

range, you have to change other things also.If you use C++20, use

`std::midpoint(lo, hi)`

(cppreference).Very Helpful Technique <3

You can optimise it more:

yup was going to say this

A doubt- While dynamically increasing hi ,won't you have to keep a check if hi exceeds its statically assigned maximum value? (else there can be a case where ,there is no answer possible ,but since you dynamically keep increasing hi ,there can be a possible solution outside the range)

Well since it's a cp problem, you're usually guaranteed that an answer does exist within the problem constraints and doesn't exceed $$$2^{64}$$$.

good technique!!!!

Pardon my lack of understanding, but when you say overflow, are you referring to "mid" or something else? If it is mid, shouldn't writing mid = low + (high-low)/2 be enough?

Yes it'll, but the author's way is kinda safer and limits the range stopping unnecessary operations.

Alright, thanks

no the author is not referring to that, he is explaining how one can define a safe range to binary search on, so that later on when we binary search on answer the sum or whatever check or predicate function will not overflow.

crazy, so simple and useful

Thanks!

What if the values of

`check(hi)`

were something like this : $$$0,0,0,\ldots,0,0,1$$$ where the only valid`hi`

would be $$$2^{63}-1$$$?Then, following this general approach, the

`hi`

would be $$$2^0, 2^1, \ldots, 2^{61}, 2^{62}$$$. But now after $$$2^{62}$$$ it would overflow when you multiply it by 2?True! But, generally, the answer doesn't reach that much. If the range is $$$2^{62}$$$ < answer < $$$2^{63}$$$ or exactly $$$2^{63}$$$-1, then can we use

`long long`

anymore? I think not, because we can't multiply more than 1 with those big values. Then we have to use`__int128`

to avoid overflow. If we use`__int128`

, then there is no issue anymore with this method.I think usually problem setters aren't psychics who try to annoy the participants, and it's CP so yes this won't happen, but if it did a single

`if`

would suffice to check for not overflowor you can

Spoileruse python

how can you be sure that the last valid value for r is not between 2^i and 2^i+1 and 2^i+1 will not overflow in check function? this sub overflow if we use this method 274332031