Я нашел следующее решение с методом множителей Лагранжа задачи Core Training в этом раунде Code Jam. Мне понравилось это решение в частности потому, что в соревнованиях по программированию очень редко встречается задачи со множителями Лагранжа.
Пусть -- заданный вектор вероятностей успеха ядр и
-- другой вектор вероятностей. Пусть
-- вероятность, что точно i ядр будут успешными, допустя что ядро i будет успешным с вероятностей pi. Тогда мы хотим найти максимум функции
![](https://espresso.codeforces.com/07dcd1999ad224ac6cf92f0b4291136eb5d976b4.png)
с ограничением
![](https://espresso.codeforces.com/fd09233cd592f1e860eb79b1f8a00e0d806f273d.png)
По методу множителей Лагранжа, мы знаем что любой максимум должен удовлетворить условию
![](https://espresso.codeforces.com/3cb623e694a0022f3b4e2bf00d1167df06e4c73e.png)
или лежить на границе множества решений (но мы сочтем этот случай попозже).
Лемма
![](https://espresso.codeforces.com/a72762ba6e204e218e517f7923754027b3428cae.png)
где -- вектор вероятностей без pi, т.е. (p1, p2, ..., pi - 1, pi + 1, ..., pn). Иными словами, частная производная f по переменной pi -- это вероятность, что K - 1 других ядр будут успешными (без ядра i).
Доказательство Леммы
Разложим члены уравнения:
![](https://espresso.codeforces.com/dfe7048e926f4f56e91c7610eb88a87019c11a36.png)
Упростим выражение:
![](https://espresso.codeforces.com/ccbfe4c080b8f276efc3638c0854d0512884a332.png)
(Конец доказательства.)
Наивное решение -- установить все pi равные друг друга. Но это невозможно потому, что мы не можем уменьшить pi меньше чем p0i. С учетом граничных условий, мы имеем для каждого ядра i три вариантов:
- Оставим pi как p0i.
- Увеличим pi до 1.
- Установим pi равные каких-то других {pj}.
Это наблюдение ограничает множесвто решений до такой степени, что мы можем его перебрать. (Ну, еще нужно несколько оптимизаий, например "увеличить pi до 1 только если pi уже велик", но это главная идея.)