http://codeforces.net/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).
anybody please help?
What is your problem? If f(p) == f(p+1) then it is neither on decreasing part nor on increasing.
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).
Yes man, you said "strictly decreasing first then some equal values and then strictly increasing", think for a little while about your own words.
That was my observation only. I need to prove my sentence.
I can't prove why this very part is true for the problem "strictly decreasing first then some equal values and then strictly increasing"
OK, so your question is about why that condition holds for that specific problem http://codeforces.net/contest/439/problem/D, not about why that condition implies ability of using ternary search. I think we misunderstood each other a bit.
Yes yes.
Can you understand me??? Please Help me out
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?