bhikkhu's blog

ternary search emergency
By bhikkhu, history, 8 years ago, In English

http://codeforces.com/contest/439/problem/D

Ternary search can only be used on strictly increasing or decreasing sequence.

But, I think the problem is special in the sense that the search space is strictly decreasing first then some equal values and then strictly increasing.

Thus, ternary search can be used here. But I need to prove that if two f(p) == f(p + 1), then the value must be the answer (if f(p) == f(p + 1), f(p) = our_answer to the problem, in case f(p) = f(p + 1) for any p).

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

anybody please help?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is your problem? If f(p) == f(p+1) then it is neither on decreasing part nor on increasing.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    My problem is this, suppose for some bound f(p) array = [3, 2, 1, 0, 0, 0, 1, 2, 3]

    Since 0 is minimum heere ternary search works(f(p) is the cost to bring all higher b values to b and lower a values to b).

    But if there were other duplicates in the f(p) array for eg. [3 2, 1, 1, 1, 1, 0, 0, 2, 3], ternary search wouldnot work.

    The question is special because only the first case will occur.

    So my question is if f(p) = f(p + 1) for the question, then f(p) = minimal.

    What I want to prove is that for the problem, there are no two different duplicates like in my above example duplicates of 1 and duplicates of 0, and whenever there are duplicates the duplicates are minimum(the answer).

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes man, you said "strictly decreasing first then some equal values and then strictly increasing", think for a little while about your own words.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        That was my observation only. I need to prove my sentence.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          I can't prove why this very part is true for the problem "strictly decreasing first then some equal values and then strictly increasing"

          → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you understand me??? Please Help me out

        → Reply
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

This had me wondering for a long time too actually. Is it possible to apply ternary search if the function isn't "strictly" convex/concave?

→ Reply