Today, I was trying to solve 626E - Simple Skewness, and I had some troubles implementing a ternary search on integers! I knew how to run a ternary search on doubles, but I didn't know how to do it on integers.
So after getting it accepted, I tried reading accepted codes of other people and I found a nice way to do it. since many of the best coders in codeforces (including tourist and Errichto) didn't use this while solving 626E - Simple Skewness, I think many people don't know about it!
So here it is!
int lo = -1, hi = n;
while (hi - lo > 1){
int mid = (hi + lo)>>1;
if (f(mid) > f(mid + 1))
hi = mid;
else
lo = mid;
}
//lo + 1 is the answer
kllp had a blog post about it.
There are also some discussions below.
Correct me if I am wrong but is using the condition r-l < 3 not good enough for ternary search on integers?
ie
//L and R are the range
while(R-L >= 3){
//implementation
}
of course not! both l + 1 and l + 2 can be the answer in this case.
Shouldn't the if condition be f(mid) > f(mid + 1)?
I'm assuming that f[x] increases and then decreases, and we want the maximum value of f[x].
Exactly.
The way it is now, if the condition f(mid) < f(mid + 1) is fulfilled, you're gonna throw everything in the interval [mid + 1, n] away, since you are setting the higher border as mid; but, the maximum f(i) is in [mid + 1, n] since f(mid + 1) is greater than f(mid).
Sorry, You're right! I just fixed it.
Thank you so much for this!
I used it to solve this problem
It's very useful :)
You're welcome! It's nice to know that I was helpful :)
Does it work correctly in case f(mid) == f(mid + 1) ? For example: f = {0, 1, 0, 0, 0}
It's impossible to run ternary search if we allow f(i) = f(i + 1).
It is still possible if we allow f(i)=f(i+1) only when f(i) is the maximum / minimum we want to find. It's a specific case, but at the same time it's fairly frequent.
Could we check f(mid-1) as well to decide where to go in such a scenario, hoping it isn't the same as f(mid) and f(mid+1).
What if it is? you check f(mid-2)? this might become linear
Just for the sake of example, i would like to put this problem https://mirror.codeforces.com/contest/1426/problem/C , we cannot ternary search it because we have f(i) = f(i+1) even when f(i) is not max or min.
Thanks! I used this trick in 631E - Product Sum and get accepted :)
My code: 16554436
How do you find the convex when i is fixed? There are a lot of local maximum points
I'm RED
How do you run ternary search if f(MID)==f(MID+1) [Or even for that matter what if f((2*LO+HI)/3)==f((LO+2*HI)/3)]??
Look up, man!