Mahdi_Jfri's blog

By Mahdi_Jfri, 17 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.

Read more »

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

By Mahdi_Jfri, 2 years ago, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

also there's another solution using dp by Kan : 32407269

Tutorial is loading...

Read more »

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

By Mahdi_Jfri, 2 years ago, In English,

Hi Codeforces!

I'd like to invite you to join Codeforces Round #446 which will be held on November 17 at 17:35 MSK.

And yes it is rated.

The contest is prepared by Omid Azadi (OmidAzadi), Mehrdad Saberi (Sa1378), Arshia Soltani (Ckodser), Aryan Esmailpour (ArEsma) and me (I honestly didn't do anything).

And also thanks to Mahdi Amiri (Amiri), AmirReza PoorAkhavan (Arpa) for helping us, Weihao Zhu (Tommyr7) for testing the round and Nikolay Kalinin (KAN) for round coordination and Mike Mirzayanov (MikeMirzayanov) for awesome platforms Codeforces and Polygon.

You will have 2 hours and 5 problems each division.

Contest theme will be about Seven Deadly Sins but the statements will be short and brief.

The scoring distribution will be posted soon and good luck and stuff.

Update 1 : The scoring for both divisions is 500 — 1000 — 1500 — 2000 — 2500.

Update 2 : The round is over. Hope everybody had fun and enjoyed it. And as you can see the round is rated so yay!

Top 5 Div1 participants :

1.moejy0viiiiiv (The only one who solved all problems)

2.Radewoosh

3.dotorya

4.SkyDec

5.ksun48

Top 5 Div2 participants:

1.shoob

2.mosthenio

3.Eragon

4.Moskupols

5.dl1997

The editorial is posted.

Read more »

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