Я нашел следующее решение с методом множителей Лагранжа задачи Core Training в этом раунде Code Jam. Мне понравилось это решение в частности потому, что в соревнованиях по программированию очень редко встречается задачи со множителями Лагранжа.

Пусть -- заданный вектор вероятностей успеха ядр и -- другой вектор вероятностей. Пусть -- вероятность, что точно i ядр будут успешными, допустя что ядро i будет успешным с вероятностей p_i. Тогда мы хотим найти максимум функции

с ограничением

По методу множителей Лагранжа, мы знаем что любой максимум должен удовлетворить условию

или лежить на границе множества решений (но мы сочтем этот случай попозже).

Лемма

где -- вектор вероятностей без p_i, т.е. (p₁, p₂, ..., p_i - 1, p_i + 1, ..., p_n). Иными словами, частная производная f по переменной p_i -- это вероятность, что K - 1 других ядр будут успешными (без ядра i).

Доказательство Леммы

Разложим члены уравнения:

Упростим выражение:

(Конец доказательства.)

Наивное решение -- установить все p_i равные друг друга. Но это невозможно потому, что мы не можем уменьшить p_i меньше чем p⁰_i. С учетом граничных условий, мы имеем для каждого ядра i три вариантов:

1. Оставим p_i как p⁰_i.
2. Увеличим p_i до 1.
3. Установим p_i равные каких-то других {p_j}.

Это наблюдение ограничает множесвто решений до такой степени, что мы можем его перебрать. (Ну, еще нужно несколько оптимизаий, например "увеличить p_i до 1 только если p_i уже велик", но это главная идея.)