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.

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

void test() {
    ll h, n;    
    cin >> h >> n;

    array<ll, 2> a[n];
    for(auto &[f, s] : a) {
        cin >> f;
    }

    for(auto &[f, s] : a) {
        cin >> s;
    }

    // Function to check if a given 'm' satisfies the problem's conditions
    auto check = [&](ll m) {
        ll sum = 0;
        for(auto &[f, s] : a) {
            ll use = (m+s-1) / s;
            sum += use * f;
        }
        return sum >= h;
    };

    ll lo = 0, hi = 1;

    // Double hi until the condition is met
    while(!check(hi)) hi *= 2;
    
    // Perform binary search within the determined range
    while(lo <= hi) {
        ll mid = (lo + hi) / 2;
        if(check(mid)) {
            hi = mid - 1;
        }
        else lo = mid + 1;
    }

    cout << lo << "\n";
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int t = 1;  cin >> t;
    while(t--) {
        test();
    }
    return 0;
}

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!