Mahdi_Jfri's blog

By Mahdi_Jfri, 3 months ago, In English,

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.

 
 
 
 
  • Vote: I like it  
  • +116
  • Vote: I do not like it  

»
3 months ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it
  1. you mean to say that it will find the minimum of "approximate" convex function?

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

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

UPD: log should be base 3/2.

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    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!

»
3 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

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