0

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-

Balasubramanian
  • 899
  • 3
  • 9
  • 16
  • convince yourself that this is a convex problem and if you plot a graph of cost vs height it will be a parabola type graph( not exactly sharp turns and same value etc can there as it is for integer points). Thus you can apply ternary search to find the global minima – advocateofnone Feb 09 '15 at 17:09

1 Answers1

3

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.
David Eisenstat
  • 64,237
  • 7
  • 60
  • 120