Метод множителей Лагранжа для "Core Training" (Code Jam 2017, Раунд 1C)

Правка ru2, от choice, 2017-05-01 01:49:40

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

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

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

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

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

Лемма

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

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

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

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

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

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

  1. Оставим pi как p0i.
  2. Увеличим pi до 1.
  3. Установим pi равные каких-то других {pj}.

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

Теги gcj, lagrange

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский choice 2017-05-02 02:34:16 5 Tiny change: 'g given that the succe' -> 'g given the succe'
en2 Английский choice 2017-05-01 01:51:06 6 Tiny change: 'e other $ p_j $ that ar' -> 'e other $ \{ p_j \} $ that ar'
ru2 Русский choice 2017-05-01 01:49:40 8
ru1 Русский choice 2017-05-01 01:44:53 2673 Первая редакция перевода на Русский
en1 Английский choice 2017-05-01 00:41:47 2982 Initial revision (published)