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

**Code Here**

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.

**Code Here**

## 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

**Code Here**

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

**Not a well drawn graph**

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.

you mean to say that it will find the minimum of "approximate" convex function?

It looks , but when will it attain minimum ? (too difficult maths!)

Hack is OK, but "Pretests passed" --> "Time Limit Exceeded on test"????

UPD: log should be base 3/2.

Acctually I think the log base should be 3/2. And like I said it may fail finding minimum.

It's not good for codeforces style contests. I actually meant there probably won't be a test that you're code fails!

Did you use this in a contest before, If so, which problems?

btw "Tof" is a hilarious name for this method :D

http://acm.timus.ru/problem.aspx?space=1&num=1874&locale=en

I can't understand why is it called "Tof", what's the joke? :p

The definition in the blog: "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."

"Tof" is a Persian word which means "to spit"