How to Find a Safe High-Value and Avoid Overflow in Binary Search

Правка en1, от tafsiruzzaman, 2024-06-12 13:59:54

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!

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский tafsiruzzaman 2024-06-12 13:59:54 3018 Initial revision (published)