Hi. First you need to know what Tof means.

It literally means spit and is used when someone rips your solution apart (imagine it written on a paper). Then you add a spit to the paper and glue it back together.

In this article I'd like to introduce Tof on ternary search.

We have a function f on [A, B] and we'd like to get the minimum position in this function. More formally we'd like to find x (A ≤ x ≤ B) such that for every y (A ≤ y ≤ B), f(x) ≤ f(y).

We call this function "Ternary-Searchable" if there exists a value K such that

• for all a , b with A ≤ a < b ≤ K, f(a) > f(b).

• for all a , b with K ≤ a < b ≤ B, f(a) < f(b).

f on real numbers

If f is defined on all real numbers then the code will be like this

for(int i = 0; i < LOG; i++)
{
    long double m1 = (A * 2 + B) / 3.0;
    long double m2 = (A + 2 * B) / 3.0;

    if(f(m1) > f(m2))
       A = m1;
    else
       B = m2;
}

    ans = f(A);

In which LOG is based on the precision you want from the answer. I use 100 or 200.

f on Integers

If f is defined on only integers you can speed it up a little bit.

while(B - A > 4)
{
    int m1 = (A + B) / 2;
    int m2 = (A + B) / 2 + 1;

    if(f(m1) > f(m2))
       A = m1;
    else
       B = m2;
}

ans = inf;

for(int i = A; i <= B; i++)
    ans = min(ans , f(i));

The Tof

So far it has been only introduction of ternary search. from now on this article won't have any proof and it's all just Tof.

Consider f as a function on integers only.

We will partition numbers on [A, B] into sets of consecutive numbers of size S. We'll call each set of consecutive numbers a Block.

g(Block) = min(f(x)) such that x is in that Block.

Now the function g we'll be "more Ternary-Searchable" than f. :D

int g(int block)
{
    int ans = inf;

    for(int i = block * S; i < (block + 1) * S && i <= B; i++)
       ans = min(ans , f(i));

    return ans;
}

int l = A / S , r = B / S + 1;

while(r - l > 4)
{
    int m1 = (2 * l + r) / 3;
    int m2 = (l + r * 2) / 3;

    if(g(m1) >= g(m2))
       l = m1;
    else
       r = m2;
}

ans = inf;

for(int i = l * S; i <= r * S && i <= B; i++)
    ans = min(ans , f(i));

This method will probably work for a function like the picture below. (hand drawn since I'm too lazy to use technology)

You should determine the S considering how bad your solution is and the time limit! (I told you it's gonna be just a Tof!!)

Feel free to add as many Tof as you can to the solution. The more Tof you add the harder it gets to hack your code.