АР
О. Ну вот тут нужно именно на операцию смотреть. Например можно увидеть, что суммарно каждый выживший элемент вобрал в себя некоторый отрезок исходного массива.
действительно, важное замечание
Size: a a a
2020 December 15
АР
чем стоит руководствоваться для нахождения всех элементов массива, которые надо сложить для того, чтобы все элементы массива были равными?
АР
проще говоря, как найти подпоследовательности, суммы элементов, которых будут равны?
М
Вечер добрый.
Какой пример применения алгоритма инверсии бинарных деревьев в практических задачах вы можете вспомнить?
Какой пример применения алгоритма инверсии бинарных деревьев в практических задачах вы можете вспомнить?
l
Вечер добрый.
Какой пример применения алгоритма инверсии бинарных деревьев в практических задачах вы можете вспомнить?
Какой пример применения алгоритма инверсии бинарных деревьев в практических задачах вы можете вспомнить?
Хз. Из мин кучи сделать Макс кучу или наоборот, если я правильно понял вопрос 🤷♂️
MB
Вечер добрый.
Какой пример применения алгоритма инверсии бинарных деревьев в практических задачах вы можете вспомнить?
Какой пример применения алгоритма инверсии бинарных деревьев в практических задачах вы можете вспомнить?
Ну просто операция реверса подотрезка обычно сводится как раз к реверсу дерева
2020 December 18
V
Всем привет. Подскажите можно ли найти пересечение массивов не сортируя их?
IZ
Всем привет. Подскажите можно ли найти пересечение массивов не сортируя их?
Ну, просто тупо поиском, но за O(N^2)
IZ
Всем привет. Подскажите можно ли найти пересечение массивов не сортируя их?
Можно через хэш-таблицу, формально — это БЕЗ СОРТИРОВКИ.
V
Можно через хэш-таблицу, формально — это БЕЗ СОРТИРОВКИ.
Окей, спасибо
A
если годятся вероятностные вещи, то можно фильтром блума
ПК
Как посчитать сумму длин всех путей дерева?
n до 10^5, нужно посчитать за секунду.
Наверное, это можно сделать динамикой, я взял dp[v] – сумма длин всех путей, полностью лежащих внутри поддерева v.
Проблема в обновлении.
Пусть мы находимся в вершине v.
Как посчитать сумму длин всех путей, которые полностью лежат в поддереве v и проходят через v?
У меня есть только одна идея: посчитать расстояние от каждой вершины до корня, потом втупую просуммировать по формуле
Но это в лучшем случае O(n²), боюсь, что это не зайдёт.
n до 10^5, нужно посчитать за секунду.
Наверное, это можно сделать динамикой, я взял dp[v] – сумма длин всех путей, полностью лежащих внутри поддерева v.
Проблема в обновлении.
Пусть мы находимся в вершине v.
Как посчитать сумму длин всех путей, которые полностью лежат в поддереве v и проходят через v?
У меня есть только одна идея: посчитать расстояние от каждой вершины до корня, потом втупую просуммировать по формуле
dist(u1, u2) = root_dist(u1) + root_dist(u2) - 2 * root_dist(lca(u1, u2))Но это в лучшем случае O(n²), боюсь, что это не зайдёт.
MB
Ну посчитай, на скольких путях лежит конкретное ребро
MB
И просуммируй по ребрам
ПК
Ну посчитай, на скольких путях лежит конкретное ребро
А, это же просто произведение размера поддерева нижней вершины и количества оставшихся вершин...
MB
Именно
ПК
Действительно, должно сработать, спасибо
A
а может быть просто рекурсивно по поддеревьям считать "сумму длин путей в нем"+"количество путей в нем"?
A
а, надо знать количество путей, которые заканчиваются в вершине поддерева
EZ
Как посчитать сумму длин всех путей дерева?
n до 10^5, нужно посчитать за секунду.
Наверное, это можно сделать динамикой, я взял dp[v] – сумма длин всех путей, полностью лежащих внутри поддерева v.
Проблема в обновлении.
Пусть мы находимся в вершине v.
Как посчитать сумму длин всех путей, которые полностью лежат в поддереве v и проходят через v?
У меня есть только одна идея: посчитать расстояние от каждой вершины до корня, потом втупую просуммировать по формуле
Но это в лучшем случае O(n²), боюсь, что это не зайдёт.
n до 10^5, нужно посчитать за секунду.
Наверное, это можно сделать динамикой, я взял dp[v] – сумма длин всех путей, полностью лежащих внутри поддерева v.
Проблема в обновлении.
Пусть мы находимся в вершине v.
Как посчитать сумму длин всех путей, которые полностью лежат в поддереве v и проходят через v?
У меня есть только одна идея: посчитать расстояние от каждой вершины до корня, потом втупую просуммировать по формуле
dist(u1, u2) = root_dist(u1) + root_dist(u2) - 2 * root_dist(lca(u1, u2))Но это в лучшем случае O(n²), боюсь, что это не зайдёт.
Центроидная?