Contribution to the Sum в олимпиадном программировании

Всем привет, у клавиатуры Кодер Арсений. Проходя одно из соревнований, мне попалась задача, которую я решил одним способом. После этого в разборе задач я увидел как раз технику "Contribution to the Sum" (перевод - "Вклад в сумму"), о которой я и хотел бы рассказать в данной статье. Перед прочтением желательно иметь хотя бы базовое представление о теории вероятностей.

Теория

Математическое ожидание

Мат. ожидание E(x)- среднее значение случайной величины. Считается как сумма произведений возможных значений на вероятность этих значений.

Приведу пример: у нас есть монеты 10 копеек, 50 копеек, 1 рубль, 2 рубля, 5 рублей и 10 рублей. Берём одну случайную монету. Задача посчитать мат. ожидание суммы, которую мы вытянем. Возвращаясь к определению мат. ожидания, получим, что

• E(x) = 0.1/6 + 0.5/6 + 1/6 + 2/6 + 5/6 + 10/6 = 3.5

Сам метод

Суть конкретно этого метода в том, что нам нужно рассмотреть каждый элемент (возможно, число, или пару, или ребро) и подсчитать, сколько раз он будет добавлен к ответу.

В статье на codeforces приводятся примеры простейших задач на эту технику. Вот одна из них: задана последовательность длины N (N ≤ 105), посчитайте тройки индексов i < j < k таких, что ai < aj и ak < aj.

Свойства мат. ожидания

Важно понимать, что E(x^2) и e(x)^2 - разные вещи. Убедиться в этом можно если вернуться к примеру с монеткой:

• E(x^2) = 0.01/6 +0.25/6 + 1/6 + 4/6 + 25/6 + 100/6 = 21.71
• E(x)^2 = (0.1/6 + 0.5/6 + 1/6 + 2/6 + 5/6 + 10/6)^2 = 12.25

Ещё важно вспомнить одно важное свойство мат. ожидания:

• E(X+Y) = E(X) + E(Y)

Ещё есть такая формула:

• E(XY) = E(X)E(Y)

Но она верна только для НЕЗАВИСИМЫХ событий. Именно поэтому в случае с монеткой E(x^2) не равно E(x)^2, ведь x и x - не независимые события.

Упорядоченные пары

Квадрат размера набора равен количеству упорядоченных пар элементов в наборе. Итак, мы перебираем пары и для каждой вычисляем вклад в ответ ("Contribution to the Sum").

Аналогично, k-я степень равна числу последовательностей (кортежей) длины k.

И опять задача: телевизор стоит $1000. В первый день его цена растёт на 1%, во второй на 2% и так далее. до пятидесятого дня. Мы покупаем его в случайный день. Чему равно мат. ожидание от цены на телик?

Концовка

Чтобы лучше понять тему, вот вам лекции по этому всему:

• По первой половине статьи (ссылка)
• По второй половине статьи (ссылка)

В этих лекциях разбираются все темы, о которых я говорил, более подробно. К тому же есть разбор приведённых мною задач и решение других задач.

Спасибо за прочтение, пока