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.
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
breakstatement 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, aslo + hican exceed theintorlong long intrange, buthi-lois guaranteed to stay in the range :)Using
mid = lo + (hi-lo)/2is good. I think usingmid = (lo + hi) / 2has no such overflow issue. Generally, the answer doesn't exceed1e18. So, in the worst case whenhi = 1e18andlo = 1e18andhi+lo = 2e18, which can easily fit inlong longrange. In this methodhiwill never reach1e18unless the answer is in1e18range. If the answer exceedslong longrange, 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 validhiwould be $$$2^{63}-1$$$?Then, following this general approach, the
hiwould 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 longanymore? I think not, because we can't multiply more than 1 with those big values. Then we have to use__int128to 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
ifwould suffice to check for not overflowor you can
use 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