Илья Дениьсев
05:26
звук и картинка есть
Иван Сафонов
01:05:34
это авторское в любом случае, поток всегда быстро работает)
Иван Сафонов
01:05:40
там же просто диниц будет
Кирилл Лебедев
01:10:12
ты в сириусе?
Шкинев Артём
01:17:21
n log центроиды?
Константин Амеличев
01:17:22
слышно
Шкинев Артём
01:18:06
не пишу
veleboks
01:18:09
может быть переливайкой по глубинам?
Кирилл Лебедев
01:18:11
переливайкой как-то? храним анордеред мапу и переливаем
veleboks
01:18:27
ну вы нам рассказывали и тут линия нужна
Кирилл Лебедев
01:22:01
эта через дек которая?
Кирилл Лебедев
01:28:22
хранить макс глубину в поддереве и приливать всё к наибольшей глубине?
Кирилл Лебедев
01:31:06
да
Никульшин Павел
01:34:35
Можно же еще спарсы написать
Никульшин Павел
01:34:49
ааа, да
Никульшин Павел
01:34:50
Ладно
Никульшин Павел
01:34:52
Нельзя)
Шкинев Артём
01:45:11
рисунок неверный
Кирилл Лебедев
01:45:24
продли левую ветку и будет верным
Иван Сафонов
01:51:35
только там на ребрах написано
Кирилл Лебедев
01:53:36
Префиксные произведения хранить. Ищем лца и отвечаем как сумму. Вместо минуса делить
Кирилл Лебедев
01:54:09
А, понятно
Кирилл Лебедев
01:54:50
хлд тогда)
Шкинев Артём
02:01:54
мы же на префиксах подсчитали
Шкинев Артём
02:02:01
а модуль не простой
Кирилл Лебедев
02:02:12
мы произведения считаем
Шкинев Артём
02:02:23
ну может быть так, что вершина LCA не префикс
Иван Сафонов
02:03:20
ДО все таки потребуется, но это не страшно (так как 1 раз обращаемся)
Шкинев Артём
02:03:39
спарсы - наш выбор
Шкинев Артём
02:04:49
а асимптотика почему нормальная будет?
Кирилл Лебедев
02:04:55
1 раз к до обращаемся
Шкинев Артём
02:04:56
потому что обращений к ДО 1
Шкинев Артём
02:04:58
?
Шкинев Артём
02:05:29
да, понял, спасибо
Кирилл Лебедев
02:06:28
а правда ли, что так можно за лог для любой ужасной функции отвечать? 1 раз к до обращаемся и много раз обращаемся к насчитанным префиксам
Кирилл Лебедев
02:06:51
понятно) hld за log тогда
Кирилл Лебедев
02:07:08
да, понятно
Кирилл Лебедев
02:07:13
я уже обрадовался)
Кирилл Лебедев
02:15:35
можно ещё раз как мы изменяем в поддереве?
Кирилл Лебедев
02:18:19
хорошо, спасибо!
veleboks
02:23:01
префиксные суммы пересчитываются за линию
veleboks
02:23:18
можно сделать эйлеров обход + фенвик на разностном массиве
veleboks
02:24:07
обратимость операции
veleboks
02:25:00
фенвик на разностном массиве, чтобы поддерживать прибавление на отрезке и гет в точке
veleboks
02:25:14
ну не разностный, это я его так назвал
Шкинев Артём
02:25:31
ans(v, u) = pr[v] + pr[u] - 2 * pr[lca(v,u)]
veleboks
02:25:32
ну да, у меня для 5 решение
veleboks
02:25:46
да, так же, как у Артема
veleboks
02:25:56
когда меняем в вершине, надо обновить поддервево
veleboks
02:26:12
для этого фенвик на эйлеровом обходе
veleboks
02:34:27
был же способ с двумя эйлеровыми обходами
veleboks
02:36:41
lca +=, v -=, u -=
veleboks
02:36:47
разностный массив на пути до корня
veleboks
02:39:21
такая же задача, как прошлая почти
veleboks
02:39:23
нет?
Кирилл Лебедев
02:39:35
нет, O(deg) изменений
veleboks
02:39:51
ну мы же умеем прибавлять на отрезке
veleboks
02:39:58
на поддереве*
veleboks
02:45:20
да
Кирилл Лебедев
02:45:22
очень тяжело осознавать это
Кирилл Лебедев
02:49:42
Ага
Кирилл Лебедев
02:52:02
Да, понятно
Кирилл Лебедев
02:52:03
Спасибо!
veleboks
02:53:57
ну два эйлеровых обхода работают
veleboks
02:55:14
а разве разваливается?
veleboks
02:55:46
а нельзя отдельно решить прибавление на поддереве и в гете просто прибавлять?
veleboks
02:56:11
тогда надо просто предыдущие два объединить
Константин Амеличев
03:26:27
))))
Константин Амеличев
03:26:41
я пытался понять откуда дядя женя вещает
Умнов Дмитрий Вячеславович
03:26:48
))))))))
Кирилл Лебедев
03:29:41
я немного опоздал, что происходит?
Кирилл Лебедев
03:29:56
а, понятно
Кирилл Лебедев
03:46:52
разностный массив
Егор Писарев
03:47:14
Прибавлять значение в нижнюю вершину, вычитать из верхней, потом обходить дерево и считать суммы снизу вверх.
veleboks
03:47:28
у нас была такая задача на первом темтуре по лца
Кирилл Лебедев
03:47:45
там был общий случай, где нужно было лца искать
Кирилл Лебедев
03:50:42
построить дерево дфс и прибавлять на пути
veleboks
03:50:44
ну можно взять остов с помощью дфс
Кирилл Лебедев
03:50:50
там где 1, там мост
Кирилл Лебедев
03:50:55
или 0, вроде
veleboks
04:12:29
его не дорассказали на площадке 1с
Кирилл Лебедев
04:12:43
4 случай был ОЧЕНЬ сложный и его не рассказали
veleboks
04:12:46
да
Кирилл Лебедев
04:15:47
я на иннопе что-то такое делал, уже не помню
veleboks
04:15:55
можно сеты в вершине хранить
veleboks
04:16:03
и делать что-то типа инсерт ирейз
veleboks
04:16:09
как += и -=
veleboks
04:17:45
хеширование ммножеств
veleboks
04:18:33
а, тогда можно прибавлять хеш ребра в каждую вершину и тогда в каждой вершине будет хеш множества накрывающих
Кирилл Лебедев
04:22:25
Можно ещё раз? Случай 2б <=> два ребра на вертикальном пути, и сумма на этом пути равна 1, да?
Кирилл Лебедев
04:25:14
и эти множества должны совпадать, что и мы проверяем через хеш
Кирилл Лебедев
04:25:14
да
Кирилл Лебедев
04:26:26
жесть задача, конечно... сами мысли про 2мост, доказательства, как надо было на туре лучше всего додумываться?
Кирилл Лебедев
04:26:42
это же совсем нетривиально
Кирилл Лебедев
04:28:29
хах)
veleboks
04:28:33
да, забавно вышло
Кирилл Лебедев
04:28:42
правда у меня 2 указателя всё равно зашли
Даниил Беляев
04:28:53
Я тл словил)
Кирилл Лебедев
04:28:59
на подзадачах
Кирилл Лебедев
04:29:00
40 баллов
Кирилл Лебедев
04:29:09
но игорь маркелов так старался с тестами
veleboks
04:29:31
там смешнее с Б2, где заходила лажа полнаяя
Кирилл Лебедев
04:29:40
привет стас
Станислав Алексеев
04:29:46
прив
veleboks
04:30:15
в темтуре будут проспекты?
Кирилл Лебедев
04:30:17
ожидаем на всеросе графы
Кирилл Лебедев
04:30:36
кстати, Б с иннопа хорошая задача на дерево дфса
Кирилл Лебедев
04:30:40
думаю, имеет место быть
Кирилл Лебедев
04:30:42
этого года
veleboks
04:31:54
так была такая задача на темтуре
veleboks
04:32:03
дистуре*
veleboks
04:32:13
а, там с кратными
Кирилл Лебедев
04:32:20
стас, напиши в чат
Кирилл Лебедев
04:32:22
че за теорема
Кирилл Лебедев
04:33:41
я скипнул геометрию 2, видимо, очень зря. 40 баллов, а могло быть 100(
Кирилл Лебедев
04:33:52
не умею писать калиперы
Кирилл Лебедев
04:34:19
там была какая-то олимпиада(
Иван Сафонов
04:34:29
Стас говорил про теорему эрдеша галлаи
Кирилл Лебедев
04:34:33
а так я не хейтер геометрии :)
Кирилл Лебедев
04:35:05
я помню, случайное множество точек было на командной тренировке к мкошп
Кирилл Лебедев
04:35:31
ого
Кирилл Лебедев
04:35:57
люди же как-то придумывают генератор случайных точек из круга
Кирилл Лебедев
04:36:32
а это хороший рандом будет? равновероятно ли
Кирилл Лебедев
04:39:11
либо придумать что-то математическое на разбор случаев
Кирилл Лебедев
04:39:21
ad-hoc придумаем
Кирилл Лебедев
04:39:54
я видел у феди в коде dsu_tree
Кирилл Лебедев
04:40:40
скинь пж, стас
Александр Чистяков
04:41:28
https://github.com/ShahjalalShohag/code-library
Кирилл Лебедев
04:41:56
Спасибо
Станислав Алексеев
04:42:58
https://blog.shahjalalshohag.com/topic-list/
veleboks
04:43:34
chinese postman problem
veleboks
04:43:42
russian postman problem
Кирилл Лебедев
04:43:53
вот дашь задачу на китайскую теорему на регион, стас
Кирилл Лебедев
04:44:02
мы тебя сразу узнаем
Кирилл Лебедев
04:45:00
тут есть permutation tree
Кирилл Лебедев
04:45:08
я об этом читал только на каком-то китайском сайте
Кирилл Лебедев
04:45:36
https://oi-wiki.org/ds/divide-combine/
Кирилл Лебедев
04:45:54
да
Кирилл Лебедев
04:46:20
aliens trick dp optimization
Кирилл Лебедев
04:46:37
когда-нибудь я это изучу
Кирилл Лебедев
04:47:39
вообще любая функция?
Кирилл Лебедев
04:48:21
кстати, тут нет ничего про кактусы
Кирилл Лебедев
04:48:35
пока, спасибо!
veleboks
04:48:40
до свидания