tafsiruzzaman's blog

How to Find a Safe High-Value and Avoid Overflow in Binary Search
By tafsiruzzaman, history, 6 months ago, In English

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:

  1. Use a Very High Value and Handle Overflow with __int128(This approach can be complex and inefficient).
  2. 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!

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

»
6 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Or one can simply put a break statement when the sum reaches beyond the desired answer (Specifically for yesterday's problem F)

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    That's true, but this method is a general approach for most binary search problems. You don't need to consider anything else.

    → Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    could you elaborate a bit please?

    → Reply
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      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 .

      → Reply
»
6 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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 :)

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    If you use C++20, use std::midpoint(lo, hi) (cppreference).

    → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Very Helpful Technique <3

→ Reply
»
6 months ago, # |
  Vote: I like it +15 Vote: I do not like it

You can optimise it more:

    while(!check(hi)) { lo = hi; hi *= 2; }
→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yup was going to say this

    → Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      6 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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}$$$.

      → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

good technique!!!!

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

crazy, so simple and useful

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks!

→ Reply
»
6 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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?

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 overflow

    → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

or you can

Spoiler
→ Reply
»
5 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply