Блог пользователя Shtrix

Автор Shtrix, 13 лет назад, По-русски
Для решения этой задачи, в первую очередь нам потребуется двоичное дерево. Естественно все его узлы хранить не удастся, соответственно прибегнем к помощи мапа/хешмапа или же пропишем свое дерево. Пускай мы для каждого поддерева храним текущее количество заряда в нем. Это несложно делается за O(H) проходом от заданной вершины к корню дерева. 

Как же найти теперь математическое ожидание?
Рассмотрим корень дерева. Пускай L - заряд левого поддерева + заряд корня, а R - заряд правого поддерева + заряд корня.  Если L == R то очевидно, что в любом случае потенциал дерева равен L (Вне зависимости от того куда путь распада пойдет). Не теряя общности допустим L < R. Тогда если путь распада пойдет в левое поддерево то потенциал дерева будет равен R. То есть с вероятностью 0.5 потенциал равен R. В другом же случае нам необходимо перейти в правое поддерево и помнить, что вероятность того что мы туда попадем уже сама по себе 0.5, а также что на предыдущем шагу мы уже оставили одну из компонент связности. Такое рассуждение необходимо применять рекурсивно, волоча за собой в рекурсии: максимальный заряд уже встретившейся компоненты связности и вероятность попадания в вершину.
В кратком псевдокоде это выглядит так:

f(curVertex, maxWas, curProbability)
{
if (curVertex is leaf) result += maxWas * curProbability;
if (L == R) result += curProbability * L;
if (L < R)
{
result += curProbability* 0.5 * R;
f(curVertex->right, max(maxWas, L), curProbability * 0.5);
}
if (L > R)
{
result += curProbability* 0.5 * L;
f(curVertex->left, max(maxWas, R), curProbability * 0.5);
}
}
Таким образом, вызовом функции
f(root, 0, 1.0) 
за время O(H) находится математическое ожидание потенциала. 

Итоговая сложность алгоритма O(HQ)
Разбор задач Codeforces Beta Round 62
  • Проголосовать: нравится
  • +23
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
prob это видимо тоже самое, что и curProbability ?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Немного проще вместо накапливания curProbability сделать, чтоб функция возвращала матожидание, которое будет равно среднему арифметическому матожиданий в двух случаях.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    На самом деле авторское решение так и выглядит. Просто в приведенном выше виде алгоритм проще объяснить, чтобы он не вызывал вопросов "а почему это верно?".