Я нашел следующее решение с методом множителей Лагранжа задачи [Core Training](https://code.google.com/codejam/contest/3274486/dashboard#s=p2&a=2) в этом раунде Code Jam. Мне понравилось это решение в частности потому, что в соревнованиях по программированию очень редко встречается задачи со множителями Лагранжа.↵
↵
Пусть $ \mathbf{p^0} = (p^0_1, p^0_2, \ldots, p^0_n) $ -- заданный вектор вероятностей успеха ядр и $ \mathbf{p} = (p_1, p_2, \ldots, p_n) $ -- другой вектор вероятностей. Пусть $ S(i, \mathbf{p}) $ -- вероятность, что точно $ i $ ядр будут успешными, допустя что ядро $ i $ будет успешным с вероятностей $ p_i $. Тогда мы хотим найти максимум функции↵
$$ f(\mathbf{p}) = \sum_{i \geq K} S(i, \mathbf{p}) $$↵
↵
с ограничением↵
$$ g(\mathbf{p}) = \sum_{i} p_i = u + \sum_{i} p^0_i $$↵
↵
По методу множителей Лагранжа, мы знаем что любой максимум $ \mathbf{p} $ должен удовлетворить условию ↵
$$ \nabla_{\mathbf{p}} f(\mathbf{p}) = \lambda \cdot \nabla_{\mathbf{p}} \left(\sum_{i} p_i\right) = \lambda \cdot (1, 1, \ldots, 1) $$↵
или лежить на границе множества решений (но мы сочтем этот случай попозже).↵
↵
#### Лемма↵
$$ \frac{\partial f}{\partial p_i} = S(K - 1, \mathbf{p}_{-i}) $$↵
где $ \mathbf{p}_{-i} $ -- вектор вероятностей без $ p_i $, т.е. $ (p_1, p_2, \ldots, p_{i - 1}, p_{i + 1}, \ldots, p_{n}) $. Иными словами, частная производная $ f $ по переменной $ p_i $ -- это вероятность, что $ K - 1 $ других ядр будут успешными (без ядра $ i $).↵
↵
#### Доказательство Леммы↵
Разложим члены уравнения:↵
$$ \frac{\partial f}{\partial p_i} = \frac{\partial}{\partial p_i} \left[ p_i \left( \sum_{i \geq K - 1} S(i, \mathbf{p}_{-i}) \right) + (1 - p_i) \left( \sum_{i \geq K} S(i, \mathbf{p}_{-i}) \right) \right] $$↵
Упростим выражение:↵
$$ \frac{\partial f}{\partial p_i} = \left( \sum_{i \geq K - 1} S(i, \mathbf{p}_{-i}) \right) - \left( \sum_{i \geq K} S(i, \mathbf{p}_{-i}) \right) = S(K - 1, \mathbf{p}_{-i}) $$↵
(Конец доказательства.)↵
↵
Наивное решение $ \nabla_{\mathbf{p}} f(\mathbf{p}) = \lambda \cdot (1, 1, \ldots, 1) $ -- установить все $ p_i $ равные друг друга. Нуо это невозможно потому, что мы не можем уменьшить $ p_i $ меньше чем $ p^0_i $. С учетом граничных условий, мы имеем для каждого ядра $ i $ три вариантов:↵
↵
1. Оставим $ p_i $ как $ p^0_i $.↵
2. Увеличим $ p_i $ до $ 1 $.↵
3. Установим $ p_i $ равные каких-то других $p_j\{ p_j \} $.↵
↵
Это наблюдение ограничает множесвто решений до такой степени, что мы можем его перебрать. (Ну, еще нужно несколько оптимизаий, например "увеличить $ p_i $ до $ 1 $ только если $ p_i $ уже велик", но это главная идея.)
↵
Пусть $ \mathbf{p^0} = (p^0_1, p^0_2, \ldots, p^0_n) $ -- заданный вектор вероятностей успеха ядр и $ \mathbf{p} = (p_1, p_2, \ldots, p_n) $ -- другой вектор вероятностей. Пусть $ S(i, \mathbf{p}) $ -- вероятность, что точно $ i $ ядр будут успешными, допустя что ядро $ i $ будет успешным с вероятностей $ p_i $. Тогда мы хотим найти максимум функции↵
$$ f(\mathbf{p}) = \sum_{i \geq K} S(i, \mathbf{p}) $$↵
↵
с ограничением↵
$$ g(\mathbf{p}) = \sum_{i} p_i = u + \sum_{i} p^0_i $$↵
↵
По методу множителей Лагранжа, мы знаем что любой максимум $ \mathbf{p} $ должен удовлетворить условию ↵
$$ \nabla_{\mathbf{p}} f(\mathbf{p}) = \lambda \cdot \nabla_{\mathbf{p}} \left(\sum_{i} p_i\right) = \lambda \cdot (1, 1, \ldots, 1) $$↵
или лежить на границе множества решений (но мы сочтем этот случай попозже).↵
↵
#### Лемма↵
$$ \frac{\partial f}{\partial p_i} = S(K - 1, \mathbf{p}_{-i}) $$↵
где $ \mathbf{p}_{-i} $ -- вектор вероятностей без $ p_i $, т.е. $ (p_1, p_2, \ldots, p_{i - 1}, p_{i + 1}, \ldots, p_{n}) $. Иными словами, частная производная $ f $ по переменной $ p_i $ -- это вероятность, что $ K - 1 $ других ядр будут успешными (без ядра $ i $).↵
↵
#### Доказательство Леммы↵
Разложим члены уравнения:↵
$$ \frac{\partial f}{\partial p_i} = \frac{\partial}{\partial p_i} \left[ p_i \left( \sum_{i \geq K - 1} S(i, \mathbf{p}_{-i}) \right) + (1 - p_i) \left( \sum_{i \geq K} S(i, \mathbf{p}_{-i}) \right) \right] $$↵
Упростим выражение:↵
$$ \frac{\partial f}{\partial p_i} = \left( \sum_{i \geq K - 1} S(i, \mathbf{p}_{-i}) \right) - \left( \sum_{i \geq K} S(i, \mathbf{p}_{-i}) \right) = S(K - 1, \mathbf{p}_{-i}) $$↵
(Конец доказательства.)↵
↵
Наивное решение $ \nabla_{\mathbf{p}} f(\mathbf{p}) = \lambda \cdot (1, 1, \ldots, 1) $ -- установить все $ p_i $ равные друг друга. Н
↵
1. Оставим $ p_i $ как $ p^0_i $.↵
2. Увеличим $ p_i $ до $ 1 $.↵
3. Установим $ p_i $ равные каких-то других $
↵
Это наблюдение ограничает множесвто решений до такой степени, что мы можем его перебрать. (Ну, еще нужно несколько оптимизаий, например "увеличить $ p_i $ до $ 1 $ только если $ p_i $ уже велик", но это главная идея.)
