How can ternary search be applied for the SPOJ challenge - KOPC12A

Question

I was trying to solve the KOPC12A problem in SPOJ.

Link to problem: http://www.spoj.com/problems/KOPC12A/

Problem in brief:

Given n buildings, each of different height(number of bricks), with each building having a cost for adding or removing a brick, find the minimum cost to make all the buildings have the same height.

After trying to solve this problem, though in vain, I came across a solution that used ternary search, after sorting the input based on their heights.

I was not able to understand how the cost for equalizing the heights of the buildings becomes unimodal(because ternary search can only be applied on unimodal functions)

This stumped me and I was not able to proceed much further.

Any insights on this is much appreciated.

Thanks-

Answer 1

To expand on sasha's comment, we can define the (strong) unimodality of a function f as the condition

for all x < y < z, f(y) < max(f(x), f(z))

and the (strong) convexity of a function f as the condition

                          z - y        y - x
for all x < y < z, f(y) < ----- f(x) + ----- f(z).
                          z - x        z - x

Let the heights of the buildings be h1, ..., hn and the unit alteration costs be c1, ..., cn. The cost f(h') to make all buildings height h' is

sum i in {1, ..., n} of ci |h' - hi|.

Now here is a sequence of propositions, each with a fairly simple proof, leading via induction to the conclusion that f is unimodal.

1. The function g where g(x) = |x| is convex.
2. For all constants h, for all convex functions g1, the function g2 where g2(x) = g1(x - h) is convex.
3. For all constants c > 0, for all convex functions g1, the function g2 where g2(x) = c g1(x) is convex.
4. For all convex functions g1 and g2, the function g3 where g3(x) = g1(x) + g2(x) is convex.
5. All convex functions are unimodal.