UVA 12407 – Speed Zones | problemsolvingnotes

The problem can be reworded as: Choose $x_i \in \mathbb{R}$ , such that

$\sum_{i = 0} ^ {N - 1} \frac{ \sqrt{100 ^ 2 + x_{i} ^ 2} }{s_i}$

is minimum, and

$\sum_{i = 0} ^ {N - 1}x_i = D$

An easy way to solve this is by using Lagrange multipliers:

$\frac{\partial}{\partial{x_i}}(\sum_{i = 0} ^ {N - 1} \frac{ \sqrt{100 ^ 2 + x_{i} ^ 2} }{s_i} - \lambda(\sum_{i = 0} ^ {N - 1}x_i - D)) = 0$

$\frac{1}{s_i} \frac{1}{2 \sqrt{100^2 + x_{i}^2}} 2x_i - \lambda = 0$

$x_i = \frac{100 \lambda s_i}{1 - \lambda^2 s_i^2}$

If we write this as:

$x_i = \frac{100 s_i}{\frac{1}{\lambda^2} - s_i^2}$

We can see that as $\lambda$ increases(decreases), $x_i$ increases(decreases), so we can do a binary search for the value of $\lambda$ that satisfies

$\sum_{i = 0} ^ {N - 1}x_i = D$

problemsolvingnotes