### Mahdi_Jfri's blog

By Mahdi_Jfri, 3 years ago, 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.

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. Comments (7)
 » 3 years ago, # | ← Rev. 3 →   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.
•  » » 3 years ago, # ^ | ← Rev. 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
•  » »
•  » » 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"