Logo

Параллель А' 2022-2023 - Shared screen with speaker view
Maxim Ryskov
01:08
+
Руслан
01:09
+
Ярослав Ноздрин
01:09
Да
Никита Гребень
01:10
+
Егор Ермолов
01:11
+
Хадзакос Николай
01:11
+
Кирилл Маглыш
01:11
+
Балабекян Андрей
01:12
+
Хамитов Хаким
01:12
+
Хадзакос Николай
01:13
+
Ожегов Леонид
01:13
+
Игорь Коломиец
01:14
+
Коновалов Ярослав
01:14
+
Константин Зюбин
01:14
+
Timofey Chicherin
01:15
+
Меликов Марат
01:15
+
Антон Мартынов
01:15
+
Никита Чистяков
01:15
+
Галим Хамитов
01:15
+
Григорий Гусев
01:16
+
Vlad
01:16
+
skimono (Камиль Шайхразиев)
01:17
+
Тимофей Ходыкин
01:17
+
Ришат Хайруллин
01:18
+
Жиганов Владислав
01:18
+
Илья Виноградов
01:18
+
Mortelman(Степан)
01:18
+
Илья Резник
01:18
+
Некрасов Станислав
01:20
+
Янко Анастасия
01:26
+
я - Ашим
01:29
не слышно
я - Ашим
01:37
слышно
Матвей Кулинич
03:58
конец в 9?
Бессолицын Максим
04:50
по Москве?
Матвей Кулинич
05:54
топ 3 любимых аниме
Сергей
06:28
когда контест откроется?
я - Ашим
07:14
видно
Хадзакос Николай
07:34
это база
Егор Ермолов
08:30
Это же хадзакос николай
Хадзакос Николай
08:36
оооо
Хадзакос Николай
08:52
егор ермолов
Егор Ермолов
09:15
Это я
Хадзакос Николай
10:25
а текстовые разборы будут?
Константин Белоусько
11:04
задачи с дистуров этого года будут совпадать с дистурами прошлого года?
Maxim Ryskov
11:22
вроде нет, они чередуют год через год
Константин Белоусько
13:11
ура
Михаил Данилов
13:13
ура
Михаил Данилов
13:15
огонь
Хадзакос Николай
13:17
siuuu
Михаил Данилов
13:24
😁
Янко Анастасия
15:28
Форму можно отправлять много раз?
Maxim Ryskov
16:29
до связи
Михаил Данилов
16:29
жестко
Хадзакос Николай
16:30
тильт
Руслан
19:03
а такие контесты будут тоже тематические ?
Никита Гребень
20:40
вова новиков момент
Константин Белоусько
20:50
Никита гребень момент
Никита Гребень
21:14
джа
Вячеслав
21:15
Зеркало для регионов будет?
Хадзакос Николай
21:28
будет тренировка на кф
Хадзакос Николай
21:32
вроде
Вячеслав
21:39
Хорошо
Николай Федоров
22:06
+
Ivan Ovcharov
22:07
+
Родион Сергеев
22:07
+
Егор Ермолов
22:08
+
Хадзакос Николай
22:08
+
Игорь Коломиец
22:08
+
Kirill Stepnov
22:08
+
Хамитов Хаким
22:08
+
Сергей
22:08
+
Константин Белоусько
22:08
+
Вячеслав
22:09
+
Даша Жилина
22:09
+
Алексей Сокольников
22:09
+
Ришат Хайруллин
22:09
+
Timofey Chicherin
22:09
+
Антон Мартынов
22:09
+
Ожегов Леонид
22:09
+
Максим Щербаков
22:10
+
Михаил Данилов
22:10
+
Никита Гребень
22:10
+
я - Ашим
22:10
-
Меликов Марат
22:10
+
Ярослав Ноздрин
22:10
+
Некрасов Станислав
22:10
+
Kiraashado(Егор Бородатов)
22:11
+
Егор Кол…
22:11
+
Александр Антропов
22:11
+
Влад Романовский
22:11
+
Маевский Матвей
22:11
+
Arina Smirnova
22:11
+
Кирилл Маглыш
22:11
+
Ильяс Сиразеев
22:11
+
Илья Резник
22:12
+
Miron Gaskov
22:12
-
Karim Motygullin
22:13
+
Алексей Волков 10В
22:14
+
Тимофей Ходыкин
22:15
+
Янко Анастасия
22:15
-
Mortelman(Фокин Степан)
22:17
-
Антон
22:18
-
Руслан
22:18
-
я - Ашим
22:19
-
Галим Хамитов
22:19
-
Кривов Георгий
22:19
-
Бессолицын Максим
22:19
-
Жиганов Владислав
22:19
-
Арсений Строков
22:19
-
Artyom Mingazov
22:20
+
Hoshi
22:20
+
Телелюхин Артём
22:22
-
Сергей
22:25
3 топ
Хадзакос Николай
22:53
🤪
Никита Гребень
22:54
и меньше бездарных условий
Константин Белоусько
23:15
а что делать если в аткодере задачи на матрицы и ффт?
Никита Гребень
23:32
скипать и решать потоки в Ex
Хадзакос Николай
23:41
)
Михаил Данилов
23:59
заботать матрицы, поплакать на ффт
Kiraashado(Егор Бородатов)
24:19
Заботать ффт, поплакать на матрицах
Михаил Данилов
24:28
😁
Хадзакос Николай
24:34
поплакать))))
Михаил Данилов
24:48
даа
Егор Городецкий
25:48
ВКОШП, кф и аткодер - это где пригождаются матрицы и ффт? Или что?
Сергей
26:09
на аткодере бывает
Хадзакос Николай
27:33
сижу в майке иннопы😎
Егор Городецкий
27:37
Чем заменить иннополис?
Михаил Данилов
27:45
высшая проба мб
Maxim Ryskov
27:50
если в 11 то вп
Хадзакос Николай
27:58
бельчонок
Miron Gaskov
28:02
Решил загуглить, что такое ффт. Теперь знаю, что ффт - это Федерация Футбола Таджикистана.
Хадзакос Николай
28:05
у нее 3 лвл
Никита Гребень
28:10
надежда машиностроения чувашии
Балабекян Андрей
28:31
У бельчонка отстойная организация
Хадзакос Николай
28:45
я шучу)))
Балабекян Андрей
29:01
Получается зря быканул
Михаил Жерневский
29:05
а что насчёт СПбГУ, ВП, всесиб?
Maxim Ryskov
29:32
всесиб это база
Хадзакос Николай
29:44
да максим, я то его слил))))
Maxim Ryskov
29:58
дядь этот год победа берешь
Хадзакос Николай
30:10
забились
Константин Белоусько
30:29
интернет-олимпиады, иоип?
Maxim Ryskov
31:48
стоит ли в форму писать про написанный кф на -150 рейта?
Телелюхин Артём
31:57
Тематические туры можно будет только неделю решать?
Сергей
32:11
у меня было -221)))
Ильяс Сиразеев
32:32
Так ты тогда специально слил, мог не сливать)
Николай Федоров
32:36
кто чаще всего будет вести занятия в онлайне?
Егор Кол…
33:36
А Вова?)
Maxim Ryskov
33:38
а вова только очно?(
Егор Городецкий
33:39
А где стоит решать задачи, которые по формату максимально приближены к задачам с олимпиад из джентельменского набора?
Матвей Кулинич
36:09
u sucker?
Егор Городецкий
36:32
Ну я лично нуб в олимпиадах, поэтому возник такой вопрос, можно ли как-то дорешивать задачи из дистуров?
Сергей
36:38
может в сборную америки берут китайцев, которые не прошли в сборную Китая?
Егор Кол…
37:27
В какое время будут перерывы? Очень хочется успевать бегать на ужин (в школе). С 18:10 до 19:10 (на хотя бы минут 15)
Егор Городецкий
37:30
А, ну, значит, можно, понял спасибо
Янко Анастасия
38:02
Дорешка тематических контестов будет учитываться в табличке?
Егор Кол…
38:05
Супер!
Ожегов Леонид
40:47
задачи на контестах упорядочены по сложности?
Матвей Кулинич
47:33
сразу видно, серьезные люди
Maxim Ryskov
47:35
получается скип
Maxim Ryskov
47:46
ок
Хадзакос Николай
47:59
на всеросе тоже скипать будешь?)
Михаил Данилов
48:13
ахахахах
Хадзакос Николай
48:17
с конца
Maxim Ryskov
48:22
с б2 я так и сделал)
Хадзакос Николай
48:27
гениц
Kiraashado(Егор Бородатов)
48:43
"ну я бы закрылся, просто щадачи слишком изяч, неинтересно"
Михаил Данилов
48:51
даа
Михаил Данилов
49:04
и вылетаешь так со школьного этапа
Константин Белоусько
50:03
только I >= 2
Хадзакос Николай
50:22
ура, мы в бесконечном цикле
Влад Романовский
51:59
Быстрее будет сначала все простые числа до корня из maxn найти а потом просто по простым бежать
Kiraashado(Егор Бородатов)
52:16
maxn до 1е18 чек
skimono(Камиль Шайхразиев)
52:37
Так у тебя тоже TL будет
Константин Белоусько
53:39
а как ты найдёшь простые до корня без деления числа?
Константин Белоусько
53:57
это вопрос Владу
Влад Романовский
55:25
Алгоритм тот же но ты перебираешь не все числа до корня а перебираешь только простые
Константин Белоусько
55:40
а как ты поймёшь, что числа простое?
Kiraashado(Егор Бородатов)
55:51
Решетом предподсчет
Влад Романовский
55:52
Решето сначала
skimono(Камиль Шайхразиев)
55:53
Ало, Евклид?
Константин Белоусько
56:07
решетом можно за лог числа раскладывать, раз н ато пошло
Влад Романовский
56:32
Ну у меня просто вчера такая проблема была, без решета не заходило)
Михаил Данилов
56:40
+-
Константин Белоусько
56:40
+
Николай Федоров
56:41
+
Miron Gaskov
56:42
+
Хамитов Хаким
56:42
_
skimono(Камиль Шайхразиев)
56:42
+
Ярослав Ноздрин
56:43
+-
Телелюхин Артём
56:43
-
Кривов Георгий
56:43
-
Kirill Stepnov
56:43
-
Soldatov Maxim
56:44
+
Никита Гребень
56:44
+
Timofey Chicherin
56:44
+
Меликов Марат
56:44
+
Руслан
56:45
-
Maxim Ryskov
56:45
+
Григорий Гусев
56:45
+
Янко Анастасия
56:45
-
Галим Хамитов
56:47
-
Вячеслав
56:47
-
Сергей
56:48
-
я - Ашим
56:49
-
Mortelman(Фокин Степан)
56:50
-
Евгений Борцов
56:51
-
Ivan Ovcharov
56:51
-
Антон
56:51
-
Иван Осипенко
56:51
-
Maxim Ryskov
56:51
-
Timofey Chicherin
56:51
-
skimono(Камиль Шайхразиев)
56:52
-
Ришат Хайруллин
56:53
-
Константин Белоусько
56:53
_
Максим Щербаков
56:54
-
Soldatov Maxim
56:54
-
Коптилин Ратибор
56:55
я не умею
10В Галявиев Арслан
56:55
-
Бессолицын Максим
56:56
-
Хадзакос Николай
56:58
+
Kiraashado(Егор Бородатов)
56:59
+
Artyom Mingazov
57:01
+-
Kiraashado(Егор Бородатов)
57:06
++
Хадзакос Николай
57:55
мне когда так в первый раз сказали, я начал хлд писать)))
Timofey Chicherin
58:29
<= sqrt(n)
Вячеслав
01:00:29
а в листке m*sqrt(m) )
Михаил Данилов
01:00:39
ну да
Руслан
01:00:40
там тоже
Михаил Данилов
01:00:41
все так
Хамитов Хаким
01:01:17
Ну тяжелые в тупую перебрать 3 вершины
Вячеслав
01:01:25
А, понял,спасибо
Константин Белоусько
01:02:16
только наверное там корень из m должен быть
Хамитов Хаким
01:02:28
дадада
Soldatov Maxim
01:04:06
теперь можно перебрать ребра тяжелой вершины в легкие и вторую тяжелую
Константин Белоусько
01:04:35
сам сказал что понял
Ильяс Сиразеев
01:05:00
Перебегаем ребра с тяжелыми обеими вершинами и даже перебираем за sqrt(m) общую легкую вершину
Ильяс Сиразеев
01:05:08
перебераем*
Балабекян Андрей
01:05:44
Двумя указателями можно перебрать
Вячеслав
01:06:03
ребро-тяжёлая-лёгкая, перебор для лёгкой
Балабекян Андрей
01:06:13
Надо ребро перебирать между легкой и тяжелой в данном случае
Матвей Кулинич
01:07:18
или только из тяжелых, не?
Maxim Ryskov
01:07:20
можно наверно по аналогии с тяжелая+легкая
Николай Федоров
01:07:23
перебрать ребро легкая-легкая?
я - Ашим
01:07:35
перебираем легкую и ее соседей, ппроверяем
Балабекян Андрей
01:07:37
Перебрать ребра между двумя легкими и двумя указателями найти количество смежных им обеим
Матвей Кулинич
01:08:07
я пропустил, 3 тяжёлых это просто тройки же перебираем?
Константин Белоусько
01:08:14
да
Miron Gaskov
01:10:02
а мы 3 тяжелых не за sqrt(n)^3 находим?
Хамитов Хаким
01:10:11
да
Kirill Stepnov
01:10:13
да
Галим Хамитов
01:10:13
да
я - не Ашим, а Миша
01:10:29
тогда уж n^2
Хадзакос Николай
01:10:35
+ тяжелая 1 на проверку
я - не Ашим, а Миша
01:10:44
кол соседей <= n?
Николай Федоров
01:10:47
мы можем разделить треугольники на треугольники из трех тяжелых и все остальные. Для трех тжелых перебираем тройки, а для всех остальных перебираем ребра, игнорирую ребра тяжелая-тяжелая и перебирая ребро из конца с легкой вершиной?
я - не Ашим, а Миша
01:11:09
нет, <=sqrt(n)
Хадзакос Николай
01:11:12
максим ты же умеешь ее решать😡
Хамитов Хаким
01:13:29
можете повторить если есть и те, и те пж
Михаил Данилов
01:13:36
да
Хамитов Хаким
01:14:24
👍🏻
Егор Кол…
01:16:50
Матрицу мы храним же? Чтобы за O(1) проверять
skimono(Камиль Шайхразиев)
01:16:58
Нельзя
Хамитов Хаким
01:17:06
памяти не хватит
Егор Кол…
01:17:13
А как за O(1) проверять
Балабекян Андрей
01:17:16
Мапу хранить надо только для тяжелых
Тимофей Ходыкин
01:17:18
unordered_set
skimono(Камиль Шайхразиев)
01:17:21
unordered_map
Егор Кол…
01:17:24
Спс)
Kiraashado(Егор Бородатов)
01:17:36
Зачем мапа
Николай Федоров
01:17:41
повтори, пожалуйста, какие треугольники могут посчитаться 2 раза и что с этим делать
Kiraashado(Егор Бородатов)
01:17:45
Если можно массив used
skimono(Камиль Шайхразиев)
01:17:52
Ну кому-как удобнее
Kiraashado(Егор Бородатов)
01:18:28
used быстрее как минимум
Kiraashado(Егор Бородатов)
01:18:42
А можно альтернативное решение рассказать? Оно не про разделение, но просто маленькое и красивое, и в относительно неожиданном месте появляется m * sqrt(m), и поэтому мне когда-то хорошо запомнилось
Хадзакос Николай
01:18:43
да и там реализация красива
Вячеслав Рощин
01:18:46
а не 6 раз?
Хамитов Хаким
01:18:47
как с помощью used?
Николай Федоров
01:18:48
хахахахахахха
Галим Хамитов
01:18:54
а как за О(1) проверить, треугольник или нет?
skimono(Камиль Шайхразиев)
01:19:35
Можешь рассказать, как ты через used будешь делать, я просто не совсем понимаю.(Егору)
Николай Федоров
01:19:35
а можно от анордеред мапы избавиться можно?
Kirill Stepnov
01:19:52
поддерживаю вопрос
Хадзакос Николай
01:19:54
да, через used
Хадзакос Николай
01:19:57
)))
Николай Федоров
01:19:57
как
Kiraashado(Егор Бородатов)
01:20:00
Ты рассмитриваешь вершину
Kiraashado(Егор Бородатов)
01:20:07
Проходишься по списку смежности
Галим Хамитов
01:20:08
понял, спасибо
Kiraashado(Егор Бородатов)
01:20:16
Помечаешь что вершина была
Kiraashado(Егор Бородатов)
01:20:30
Потом смотришь вторую вершину, тоже также помечаешь
Kiraashado(Егор Бородатов)
01:20:44
Потом когда их обработал размечаешь обратно
Хадзакос Николай
01:22:57
сейчас просто гениальные вещи будут
Kirill Stepnov
01:25:36
вау
Галим Хамитов
01:25:41
крутяк
skimono(Камиль Шайхразиев)
01:25:42
300 IQ
Егор Городецкий
01:25:47
ойойойойой
Хамитов Хаким
01:25:54
не понял(
Хадзакос Николай
01:26:05
смотри
Хадзакос Николай
01:27:26
у тебя переходы всегда sqrt(m) потому что:1. левее у тебя "легкие вершины"(их степень O(sqrt(m)))2. правее "тяжелые вершины"(их sqrt(m))
Хамитов Хаким
01:27:32
все
Хамитов Хаким
01:27:34
понял
Михаил Данилов
01:29:45
гениально
Kirill Stepnov
01:30:05
это ведь и в первом способе использовать можно ?
Егор Городецкий
01:30:09
Высокая концентрация гениального решения
Maxim Ryskov
01:31:15
это разве не n*m?
Галим Хамитов
01:31:46
m
Maxim Ryskov
01:32:32
а понял ок
Галим Хамитов
01:32:58
спасибо
Щербаков Сергей
01:33:02
спасибо
Хадзакос Николай
01:33:10
но это без кратных ребер)
Галим Хамитов
01:34:22
идеально
Галим Хамитов
01:34:45
когда перерыв?
Николай Федоров
01:34:49
а вершина v смежна сама с собой?
Константин Белоусько
01:35:04
сказали же после 18
Хамитов Хаким
01:35:07
только если петля
Хадзакос Николай
01:35:09
ну ты просто опускаешь этот случай по факту
Вячеслав Рощин
01:35:15
А если не дерево решение отличается?
я не Ашим, а Миша
01:35:31
нужно ифать
Вячеслав Рощин
01:35:37
Тяжёлый лёгкий?
Хадзакос Николай
01:35:41
ты же cnt обновляешь в позициях правее
Soldatov Maxim
01:35:56
а асимптотика гениального решения от кратных ребер не меняется?
Галим Хамитов
01:38:00
нет
Константин Белоусько
01:40:54
идея в том чтобы асимптотика была nsqrtn а не msqrtm
zitraks
01:44:05
f
Михаил Данилов
01:44:06
зависло
Егор Ермолов
01:44:07
Хамитов Хаким
01:44:07
лаги
Галим Хамитов
01:44:07
блин(
Егор Городецкий
01:44:09
RIP
Вячеслав Рощин
01:44:10
+
я не Ашим, а Миша
01:44:10
залагали
Влад Романовский
01:44:11
F
Егор Ермолов
01:44:13
F
Руслан
01:44:14
F
Artyom Mingazov
01:44:17
f
Ильяс Сиразеев
01:44:19
Думал у меня у одного уже траблы с инетом
Maxim Ryskov
01:44:20
все норм теперь
Kiraashado(Егор Бородатов)
01:44:26
Ура восстановилось
Галим Хамитов
01:44:34
всё хорошо
Михаил Данилов
01:44:43
а как обращаться - на ты или на вы?
Михаил Данилов
01:44:48
ок
Хадзакос Николай
01:46:04
Ахо-Корасик)
Константин Белоусько
01:46:09
чел ты
Вячеслав Рощин
01:46:14
+
Kiraashado(Егор Бородатов)
01:46:15
Из пушки по воробью
Балабекян Андрей
01:46:23
Длин не больше sqrt(s)
Хадзакос Николай
01:46:39
я ее не смог решить🙃
Maxim Ryskov
01:46:46
суфф автомат)
Хадзакос Николай
01:46:50
ахахахахахахахахахаахах
Михаил Данилов
01:47:17
для 🅱️edolag
Балабекян Андрей
01:47:22
Можно честно для каждой отдельной длины проходиться и хеши кидать в мапуЕсли пришла строка длины k и мы уже до этого обрабатывали эту длину, то просто достанем ответ, иначе пройдемся по всей строке
Егор Кол…
01:47:38
Я чет туплю, а хеши нельзя
avevad
01:47:39
суфавтомат значит
Константин Белоусько
01:47:44
без хешей
Кирилл Маглыш
01:47:49
Суфматом онлайн можно вроде
Балабекян Андрей
01:48:00
Ну тогда мапа <string, int>
Николай Федоров
01:48:04
в онлайне не получится предпосчитать хеши видимо
Константин Белоусько
01:48:10
получится
Егор Кол…
01:48:18
Будет O(tS)
Константин Белоусько
01:48:21
нет
я не Ашим, а Миша
01:48:21
-
Егор Кол…
01:48:22
с хешами
Антон
01:48:23
-
Хамитов Хаким
01:48:24
_
Егор Кол…
01:48:28
-
Хадзакос Николай
01:48:29
не умею корневой
Жиганов Владислав
01:48:31
-
Коновалов Ярослав
01:48:32
-
Руслан
01:48:32
-
Галим Хамитов
01:48:33
-
Soldatov Maxim
01:48:33
-
Иван Осипенко
01:48:34
-
Timofey Chicherin
01:48:34
-
Kirill Stepnov
01:48:36
-
Михаил Данилов
01:48:37
-
Максим Щербаков
01:48:37
-
Янко Анастасия
01:48:37
-
Никита Гребень
01:48:40
-
Даша Жилина
01:48:41
-
Maxim Ryskov
01:48:42
-
Балабекян Андрей
01:48:47
Для каждой длины ты только один раз пройдешься по строке, а длин не больше корня
Никита Гребень
01:49:25
а омг длин не больше корня реально же
Егор Кол…
01:49:27
Поступает строка, хеш нужно найти за ее длину
Егор Кол…
01:49:34
так что хеш -
Галим Хамитов
01:49:43
я думаю нужно подсчитать кол во символом в строке s
Kiraashado(Егор Бородатов)
01:49:57
А мы можем хеши?
Илья Виноградов
01:49:59
хеши для мелких, а для длинных z-функция?
Балабекян Андрей
01:50:02
O(|t| * sqrt(s) + s)
Галим Хамитов
01:50:07
именно колво ашек, бэшек, цэшек и тд
Kiraashado(Егор Бородатов)
01:50:11
Для длинных втупую
Kiraashado(Егор Бородатов)
01:50:17
Для медких предподсчет
Kiraashado(Егор Бородатов)
01:50:47
Либо просто когда новадлина считаем хеши для неё
Константин Белоусько
01:50:50
тяжёлая строка, если её длина больше sqrtS, а лёгкая иначе. Все лёгкие строки можно сложить в unordered_map, а для тяжёлых строк, например, юзать КМП
Николай Федоров
01:51:12
если для больших считать КМП, то асимптотика будет другая
Константин Белоусько
01:51:22
нет
Константин Белоусько
01:51:34
у тебя суммарная длина строк + sqrtS * t
Николай Федоров
01:51:35
строка может быть длины O(s)
Константин Белоусько
01:51:40
и что
Константин Белоусько
01:52:13
(s1 + t) + (s2 + t) + … + (sk + t) = (s1 + s2 + … + sk) + t * k
Константин Белоусько
01:52:24
k = sqrtS
Николай Федоров
01:52:31
согл
Галим Хамитов
01:52:44
нет
Янко Анастасия
01:53:05
Можно ещё раз про большие строки?
Галим Хамитов
01:53:09
+
Никита Гребень
01:53:19
слышу эхо сунц мгу
Maxim Ryskov
01:53:20
о с бором топ
Михаил Данилов
01:53:20
Николай на стадионе сидит
Константин Белоусько
01:53:24
просто для каждой большой строки используешь кмп
Галим Хамитов
01:54:59
да
Вячеслав Рощин
01:55:04
Можете повторить как решать для тяжёлых?
Янко Анастасия
01:55:08
Да
Вячеслав Рощин
01:55:20
Да
Галим Хамитов
01:56:04
хэшами можно?
Галим Хамитов
01:56:17
ок
Maxim Ryskov
01:57:07
от коли было
Хамитов Хаким
01:57:44
капец, что такое бор(
skimono(Камиль Шайхразиев)
01:57:58
B'
Хамитов Хаким
01:57:58
👍🏻
Хадзакос Николай
01:58:01
топовая вещь
Галим Хамитов
01:58:40
мне кажется без бора легче, нет?
Николай Федоров
01:58:51
бор работает быстрее хешей
Hoshi
01:58:56
это только при офлайн запросах же, да
Хадзакос Николай
01:59:02
бор тема
Хамитов Хаким
01:59:12
давайте
Илья Виноградов
01:59:20
суфф автомат?????
Янко Анастасия
01:59:31
Почему с бором быстро работает?
Янко Анастасия
02:01:06
А, хорошо
Влад Романовский
02:01:44
А ахо корасиком офлайн тоже можно?
Константин Белоусько
02:02:56
всего лёгких подстрок у t ровно t + (t - 1) + … + (t - sqrtS + 1) = (2t - sqrtS + 1) * sqrtS / 2 = tSqrtS - S + sqrtS / 2, а их суммарная длина = tS - 1^2 - 2^2 - … - sqrtS^2 + 1 + 2 + … + sqrtS = tS - SsqrtS + S
Галим Хамитов
02:05:13
да
Kirill Stepnov
02:05:14
д
Никита Гребень
02:05:16
+
Антон
02:05:16
+
я не Ашим, а Миша
02:05:19
+
Константин Белоусько
02:05:20
+
Timofey Chicherin
02:05:21
+
Kirill Stepnov
02:05:21
+
Ярослав Ноздрин
02:05:22
+
Хамитов Хаким
02:05:27
+
Maxim Ryskov
02:07:51
чет решения онлайн легче чем офлайн
Влад Романовский
02:08:01
Ага))
Maxim Ryskov
02:08:03
решение*
Янко Анастасия
02:09:05
Мы просто храним unordered_map для каждой длины?
Антон Мартынов
02:10:27
А почему решение с бором нельзя использовать для онлайн?
Константин Белоусько
02:10:41
потому что бор нужно на чём-то построить
Kirill Stepnov
02:10:50
потому что нельзя будет построить бор на всех строках сразу
Vladislav Kazantsev
02:11:21
Пацаны, кто в бравл (новая платформа для решения задач)?
Галим Хамитов
02:11:24
Спасибо
Константин Белоусько
02:11:31
блин, можно ещё 5 задачу
zitraks
02:11:40
ссылку кинь
Антон Мартынов
02:11:57
а почему нельзя взять все легкие подстроки t и на них построить бор?
Константин Белоусько
02:11:59
просто у нас ужин в 18:40
Хамитов Хаким
02:12:00
приятного всем аппетита!
я не Ашим, а Миша
02:12:01
сколько перерыв?
Miron Gaskov
02:12:02
поспим 20минут и дальше ботать)
Михаил Данилов
02:12:05
всем приятного аппетита
Николай Федоров
02:12:14
а у меня в 19 ужин!!
Галим Хамитов
02:12:15
только ничего не проходите без иеня
Хадзакос Николай
02:12:16
о, 5 задача имба
Dmitrii Umnov
02:12:17
Перерыв на 20 минут, до 18:35
skimono(Камиль Шайхразиев)
02:12:20
Спасибо
Maxim Ryskov
02:25:05
лучше на авиках
skimono(Камиль Шайхразиев)
02:25:22
Повтори
Руслан
02:27:11
у кого то микро включен
Хадзакос Николай
02:31:44
ку
Николай Федоров
02:31:47
+
Maxim Ryskov
02:31:47
+
Балабекян Андрей
02:31:47
+
Вячеслав Рощин
02:31:48
ку
Арсений Строков
02:31:48
ку
Miron Gaskov
02:31:48
+
Hoshi
02:31:48
+
Ярослав Ноздрин
02:31:49
+
Ришат Хайруллин
02:31:49
+
Влад Романовский
02:31:49
+
Коновалов Ярослав
02:31:49
+
Егор Ермолов
02:31:50
+
Егор Городецкий
02:31:50
+
Timofey Chicherin
02:31:50
+
Ильяс Сиразеев
02:31:51
+
Антон
02:31:52
+
Кривов Георгий
02:31:54
+
Янко Анастасия
02:31:56
+
я не Ашим, а Миша
02:31:57
+
Даша Жилина
02:31:57
+
Антон Мартынов
02:31:58
+
Хамитов Хаким
02:32:14
+
Галим Хамитов
02:32:25
+
Kirill Stepnov
02:33:39
извиняюсь
Галим Хамитов
02:34:24
+
Maxim Ryskov
02:34:26
+
Kirill Stepnov
02:34:26
-
Даша Жилина
02:34:27
+
Коновалов Ярослав
02:34:28
+
Вячеслав Рощин
02:34:28
-
Ярослав Ноздрин
02:34:28
+
Влад Романовский
02:34:28
-
Ожегов Леонид
02:34:28
-
Максим Щербаков
02:34:29
-
Меликов Марат
02:34:29
-
Бессолицын Максим
02:34:29
-
Никита Гребень
02:34:29
видел на центроиды
Михаил Данилов
02:34:29
+-
Некрасов Станислав
02:34:29
-
Балабекян Андрей
02:34:29
+
Руслан
02:34:29
-
Янко Анастасия
02:34:30
-
Mortelman(Фокин Степан)
02:34:30
­-
Арсений Строков
02:34:30
+
Хадзакос Николай
02:34:30
+
Хамитов Хаким
02:34:30
+
Кривов Георгий
02:34:30
+
Николай Федоров
02:34:31
+
Егор Городецкий
02:34:31
-
Александр Антропов
02:34:31
-
Timofey Chicherin
02:34:31
+
skimono(Камиль Шайхразиев)
02:34:31
-
Антон Мартынов
02:34:32
+
Евгений Борцов
02:34:32
+
Андрей Килин
02:34:33
+
Антон
02:34:33
-
Григорий Гусев
02:34:34
-
Artyom Mingazov
02:34:36
-
Настоятель в женском платье
02:34:36
-
10В Галявиев Арслан
02:35:25
она офлайн или онлайн?
Балабекян Андрей
02:35:37
Пофигу вроде
Галим Хамитов
02:36:07
может для каждой вершины посчитать кол во чёрных, смежных с ней?
Сергей
02:36:26
корнячка по запросам?
Сергей
02:36:38
а ну да
Галим Хамитов
02:37:09
понял
skimono(Камиль Шайхразиев)
02:37:10
Типо с Rebuild через каждые sqrt запросов?
Хадзакос Николай
02:37:19
ну похоже да
Kiraashado(Егор Бородатов)
02:38:12
LCA за О(1) - приятно
Kiraashado(Егор Бородатов)
02:38:19
Коля не прав
Хадзакос Николай
02:38:22
ой тьфу
Kiraashado(Егор Бородатов)
02:38:36
Знали
я не Ашим, а Миша
02:38:37
"LCA за О(1) - приятно"согл
skimono(Камиль Шайхразиев)
02:38:38
Ну корнячку знали
Хадзакос Николай
02:38:59
я забыл про спарсы
Хадзакос Николай
02:39:02
это приятно да
Хадзакос Николай
02:39:09
лца за o(1)
Хадзакос Николай
02:39:20
я просто бинапы люблю))))
skimono(Камиль Шайхразиев)
02:39:34
+
Artyom Mingazov
02:39:38
😀
skimono(Камиль Шайхразиев)
02:40:13
Типо смайл клоуна не нашёл?
я не Ашим, а Миша
02:42:47
n * sqrt(n)?
я не Ашим, а Миша
02:43:05
а, нет, n
Николай Федоров
02:44:37
можно еще раз какой предподсчет делаем?
Янко Анастасия
02:45:02
А чтобы расстояние узнавать нужен LCA?
Галим Хамитов
02:45:11
ага
Николай Федоров
02:45:32
понял
Хадзакос Николай
02:46:03
ну да, через лца ты просто найдешь глубину lca и просуммируешь разности длин
Хадзакос Николай
02:46:14
это я насте
Янко Анастасия
02:46:30
Ок, спасибо
10В Галявиев Арслан
02:47:47
а почему в асимптотике корень из n, может быть корень из q должен быть?
Руслан
02:48:04
лагает сильно
Хамитов Хаким
02:48:11
ага
Михаил Данилов
02:48:18
уже норм
Михаил Данилов
02:48:35
а, нет
10В Галявиев Арслан
02:48:38
да стало
Хамитов Хаким
02:48:41
(
Галим Хамитов
02:48:41
блин(
Вячеслав Рощин
02:48:42
F
Егор Городецкий
02:48:45
F
Антон
02:48:45
упало
Руслан
02:48:45
F
Kirill Stepnov
02:48:46
(
я не Ашим, а Миша
02:48:47
лаги
Андрей Килин
02:48:47
f
Влад Романовский
02:48:48
F
Галим Хамитов
02:48:53
всё норм
Михаил Данилов
02:48:54
сейчас норм
я не Ашим, а Миша
02:48:56
норм
Влад Романовский
02:48:58
норм
10В Галявиев Арслан
02:49:05
да услышал
Хамитов Хаким
02:50:14
айайай
Руслан
02:50:17
F
Вячеслав Рощин
02:50:33
Свет походу съел инет(
Руслан
02:50:38
))
Михаил Данилов
02:50:39
ахахахах
я не Ашим, а Миша
02:50:41
)
Галим Хамитов
02:50:54
: D
Руслан
02:51:25
+
Ожегов Леонид
02:51:26
+
Балабекян Андрей
02:51:27
Слышно
я не Ашим, а Миша
02:51:27
норм
Влад Романовский
02:51:28
+
Вячеслав Рощин
02:51:28
Пока хорошо
Меликов Марат
02:51:29
+
Галим Хамитов
02:51:33
отлично
Балабекян Андрей
02:52:11
Да можно без видео наверное, чтобы не лагало
Вячеслав Рощин
02:52:24
Ну картинка лагает)
Вячеслав Рощин
02:52:27
у видео
Алексей Сокольников
02:53:04
может быть minimal excluded?
Хадзакос Николай
02:54:24
можно наверное разбивать на блоки по sqrt(n) и закидывать все эти mex в set, тогда очевидно, что ответ будет больше максимального меха в этом сете
Хадзакос Николай
02:54:39
или не очевидно
Галим Хамитов
02:55:01
не очев
Вячеслав Рощин
02:55:04
Мо же?
skimono (Камиль Шайхразиев)
02:55:10
Ну, это если ты про МО знаешь
Хадзакос Николай
02:55:21
жесть я дурик...
Алексей Сокольников
02:55:23
перс до))
skimono (Камиль Шайхразиев)
02:55:26
Так его уже озвучили
Вячеслав Рощин
02:55:27
Ну так я не рассказываю же
Хадзакос Николай
02:55:30
я забыл про мо
Хадзакос Николай
02:55:31
тильт
Хадзакос Николай
02:55:33
тильт
Хадзакос Николай
02:55:34
тильт
Балабекян Андрей
02:55:37
"Давайте, придумывайте МО"
Алексей Сокольников
02:55:37
там тоже можно, насколько я помню
Алексей Сокольников
02:55:51
запоминаем ласт вхождение числа
Галим Хамитов
02:55:56
нет
Алексей Сокольников
02:55:58
и ищем первое вхождение <= l_i
Хадзакос Николай
02:56:21
да, факты говорит
Галим Хамитов
02:56:26
может отсортировать запросы как-нибудь?
Никита Гребень
02:56:41
можно кажется в перс до по возрастанию значений ставить единички в позиции и для каждого отрезка бинарить ответ
Илья Резник
02:58:06
Легенда
Хадзакос Николай
02:58:13
задача 8 - 3D мо
Хадзакос Николай
02:58:16
гг
Вячеслав Рощин
02:58:30
Эх,а я не знаю 3D мо(
Илья Виноградов
02:59:24
храним битсеты в каждом блоке, и потом делаем битовый или, а для ответа ищем первый 0
Балабекян Андрей
02:59:52
Звучит классно
Константин Белоусько
03:00:04
Мо
Никита Чистяков
03:00:07
битовой или для битсета за длину работает не?
я не Ашим, а Миша
03:02:32
может как-нибудь декартом
skimono (Камиль Шайхразиев)
03:02:40
Фууу
Константин Белоусько
03:02:47
Мо
Александр Антропов
03:03:53
декартово дерево
Балабекян Андрей
03:03:53
ДО
Хамитов Хаким
03:03:54
дд?
я не Ашим, а Миша
03:03:58
ДД
Илья Виноградов
03:04:01
корнячка?
я не Ашим, а Миша
03:04:03
я писал
Ожегов Леонид
03:04:10
сет + массив cnt
Вячеслав Рощин
03:04:23
ну для log можно и фенвик сделать
Timofey Chicherin
03:04:30
set с элементами, которых нет в множестве + map c количествами вхождений каждого элемента
Даша Жилина
03:05:08
Зачем map если можно просто multiset
Константин Белоусько
03:05:11
можно даже не map, а обычный массив длины n + 1, т. к. mex <= n
Антон Мартынов
03:06:15
Кстати мех на отрезке в оффлайне можно ДОшкой
Алексей Сокольников
03:06:30
на личном опыте проверено, что с битсетами летает
Алексей Сокольников
03:06:43
раз в 20 быстрее битсетов
Никита Чистяков
03:07:00
что)
Алексей Сокольников
03:07:11
сетов*
Алексей Сокольников
03:07:24
давайте проверим, зайдет ли МЕХ на дереве с битсетами у вас?)))
Балабекян Андрей
03:09:07
O(n)
Руслан
03:09:08
0(n)
Михаил Данилов
03:09:12
nlogn
Kirill Stepnov
03:09:13
nlogn
Балабекян Андрей
03:09:16
nlog
Галим Хамитов
03:09:19
О(n log n)
Maxim Ryskov
03:09:20
o(nlogn)
я не Ашим, а Миша
03:09:20
n log n
Антон Мартынов
03:09:24
n*(время работы структуры)
Янко Анастасия
03:09:30
Как удалять и добавлять, можно ещё раз?
Руслан
03:10:03
а почему мы добавляем не за О(1) ?
Янко Анастасия
03:10:09
Нет, всмысле как пересчитать ответ?
Михаил Данилов
03:10:35
у тебя есть сет чисел, которых нет
Михаил Данилов
03:10:45
ответ это минимальный элемент в сетике
Руслан
03:10:59
а все хорошо
Янко Анастасия
03:11:06
А, поняла
Kirill Stepnov
03:18:46
красиво
Руслан
03:19:49
можно еще раз кратко
Галим Хамитов
03:19:58
+
Галим Хамитов
03:20:10
только самое главное в итоге решение
Галим Хамитов
03:20:17
по порядку
Галим Хамитов
03:21:33
понятно
10В Галявиев Арслан
03:21:35
кок
Галим Хамитов
03:21:37
спасибо
Галим Хамитов
03:21:47
ок
Янко Анастасия
03:23:26
Можно ещё раз, за что отвечает блок cnt?
Галим Хамитов
03:24:00
(
я не Ашим, а Миша
03:24:02
F
Янко Анастасия
03:24:07
Лагает(
Никита Гребень
03:24:08
f
Руслан
03:24:10
F
Михаил Данилов
03:24:15
сейчас норм
Галим Хамитов
03:24:16
всё норм
я не Ашим, а Миша
03:24:21
норм стало
Руслан
03:24:22
+
Руслан
03:24:59
опять пропадаете
Галим Хамитов
03:25:09
ничё не понятно
Галим Хамитов
03:25:35
нет, не понятно, что ты говоришь
Галим Хамитов
03:25:38
решение понятно
Руслан
03:25:49
уже все хорошо
Галим Хамитов
03:25:51
ага
Михаил Данилов
03:25:52
сейчас хорошо слышно
я не Ашим, а Миша
03:25:55
ага
Михаил Данилов
03:31:49
глина
Никита Гребень
03:32:33
глина
Ожегов Леонид
03:32:46
крутая идея про то, что в нечетных блоках нужно по-другому сортить
Никита Гребень
03:32:50
+
Руслан
03:33:00
можете еще раз код показать
Руслан
03:33:33
чуть выше
Руслан
03:33:41
все сппсибо большое
Руслан
03:33:56
не я просто прослушал)
Михаил Данилов
03:36:53
понятно
Галим Хамитов
03:36:53
понятно на 10
Kirill Stepnov
03:36:53
классная идея
Янко Анастасия
03:36:57
Понятно
Miron Gaskov
03:36:59
понятно
Константин Белоусько
03:39:00
но есть один нюанс
Егор Кол…
03:40:41
В 6
Егор Городецкий
03:40:45
это же задача 6 была
Михаил Данилов
03:40:56
да
Михаил Данилов
03:40:59
мы на 8 сразу
Егор Кол…
03:41:25
Время
Вячеслав Рощин
03:41:35
время операции
Вячеслав Рощин
03:42:08
Запрос любой или именно последнего обновления?
Вячеслав Рощин
03:42:21
Понял
Коптилин Ратибор
03:43:48
t разве не до q
Вячеслав Рощин
03:43:52
Почему t от 0 до n, не понял просто
Янко Анастасия
03:48:55
В каком порядке сортировать запросы?
Руслан
03:50:10
c - это то что было константой ?
Галим Хамитов
03:50:27
да
Михаил Данилов
03:50:30
можно кратко в целом алгоритм, пожалуйста?
Ожегов Леонид
03:50:40
+
Антон
03:50:41
+
Константин Белоусько
03:50:44
формула включений исключений?
Антон Мартынов
03:51:38
Может по времени то в одну сторону, то в другую
Балабекян Андрей
03:52:00
Типа если сумма номеров блоков четна, то в одну, иначе в другую
Балабекян Андрей
03:52:04
?
Никита Чистяков
03:52:49
я кстати слышал про оптимизацию мо с кривой гильберта)))
Михаил Данилов
03:53:44
ок, понял
Янко Анастасия
03:53:51
Структуру такую же как и в прошлой задаче?
Янко Анастасия
03:54:05
Изменение только в сортировке запросов?
я не Ашим, а Миша
03:54:39
хранить прошлые состояния
Илья Виноградов
03:55:38
а нам не легче здесь использовать корневую по запросам?
Илья Виноградов
03:55:58
в каждом блоке делаем обычный мо
Антон Кожевников
03:56:30
То есть мы просто как в обычном мо отсортим запросы на мех по l,r,t, и будем двигаться, где шаг по t это просто изменить состояние структуры за быстро?
Илья Виноградов
03:56:30
а если размер блока сделать меньше?
я не Ашим, а Миша
03:57:07
а как часто этот алгоритм применяется?
Илья Виноградов
03:58:05
пусть размер блока - q / k.
Галим Хамитов
03:58:13
надеюсь не часто
Телелюхин Артём
03:58:18
А как за быстро структуру обновлять?
Никита Гребень
03:58:36
некоторые задачи которые решаются по умному можно свести к чему то тупому с мо
Вячеслав Рощин
03:58:45
+
Телелюхин Артём
03:59:05
Да
Янко Анастасия
03:59:09
Мы для каждого блока храним отдельную структуру?
Maxim Ryskov
03:59:24
а мы опять тут юзаем корневую на массиве как в 6?
Михаил Данилов
04:00:28
crazy
я не Ашим, а Миша
04:00:28
будет такая задача в контесте?
Никита Гребень
04:00:29
C короткого отбора открытки решалась через мо
Балабекян Андрей
04:00:31
А сильная разница от того решения, что я пройдусь за O(n) на запрос?
Михаил Данилов
04:00:31
реально встречается
Алексей Сокольников
04:00:42
там есть))
я не Ашим, а Миша
04:00:42
спасибо
Илья Виноградов
04:00:43
тогда у нас внутри каждого блока мо работает за n * n / k, тогда где k - размер блока, тогда для каждого из k запросов мы проверяем k запросв изменения. тогда асимптотика q / k * (k * k + n * 2 / k)) и при k = n ^ (2 / 3) это будет n ^ (5 / 3)
Илья Виноградов
04:01:44
размер блока - k
Илья Виноградов
04:02:44
понял
Янко Анастасия
04:03:55
Понятно
Арсений Строков
04:04:01
А почему это быстро работает?
Арсений Строков
04:05:07
мы же можем для каждого запроса t двигать долго
Арсений Строков
04:05:31
аок
Янко Анастасия
04:05:38
Ещё раз, откуда 2/3?
Вячеслав Рощин
04:06:37
Доказательство оставляем читателю в качестве упражнения
Kirill Stepnov
04:06:47
* задачки на ночь
Никита Чистяков
04:07:23
идея про корневую по запросам + мо кстати в этой статье была https://codeforces.com/blog/entry/83630 и там как раз ничего про изменения не говорилось)
Николай Федоров
04:07:25
сложно
Никита Гребень
04:09:25
сложно
Никита Гребень
04:09:57
на отрезке бы научиться инверсии искать за sqrt
Николай Федоров
04:10:28
на отрезке можно фенвиком с МО
Антон Кожевников
04:10:39
Давайте найдём lca вершин и решим задачу для одной половины пути и обратную задачу для другой половины пути. Будем делать предподсчёт из корня и если глубина какой то из вершин кратна c=sqrt(n), то заполним массив cnt для пути от неё до вершины, которая находится на c вершин сверху. Когда будем считать ответ, то путь от вершины до lca разобьется на куски длины sqrt(n) и какие-то хвосты длины меньше c, куски посчитаем массивами cnt с префсуммами, а хвосты втупую
я не Ашим, а Миша
04:11:54
можно с merge sort?
Антон Кожевников
04:11:56
в смысле складывать
Хамитов Хаким
04:11:58
+
я не Ашим, а Миша
04:12:18
путь сортировать и считать
я не Ашим, а Миша
04:12:51
эта ассимптотика на запрос?
Никита Гребень
04:12:59
понятно как за sqrt log через до но непонятно что сделать для вертикальных путей
Хамитов Хаким
04:13:33
до по эйлеровому пути?
я не Ашим, а Миша
04:13:45
)
Галим Хамитов
04:13:46
ой
я не Ашим, а Миша
04:13:47
f
Руслан
04:13:47
F
Maxim Ryskov
04:13:48
f
Hoshi
04:13:48
лол
Алексей Сокольников
04:13:50
F
Никита Гребень
04:13:51
pominki
Илья Резник
04:13:51
F
Антон Мартынов
04:13:53
(
skimono (Камиль Шайхразиев)
04:13:53
F
Вячеслав Рощин
04:13:53
F
Хамитов Хаким
04:13:53
айайай
Фокин Степан
04:13:57
F
Bessolytsun Maksim
04:13:57
F
Балабекян Андрей
04:13:57
F
Kirill Stepnov
04:13:58
(
Михаил Данилов
04:13:58
😪
Вячеслав Рощин
04:13:59
свет всё же победил
Арсений Строков
04:13:59
кто в бравл?
Сергей
04:14:01
F
Хамитов Хаким
04:14:03
я
Галим Хамитов
04:14:17
он устал?
Maxim Ryskov
04:14:22
сеня какой бравл
zitraks
04:14:30
🕯️
Галим Хамитов
04:14:59
грустно, вдруг что-то случилось
skimono (Камиль Шайхразиев)
04:15:02
🥀
Хамитов Хаким
04:15:04
кажется что то с lca с предмотсчетом за nlogn и до
Hoshi
04:15:27
🩹
skimono (Камиль Шайхразиев)
04:15:36
Лол, я организатором стал
Руслан
04:15:47
теперь ты батька тут
Maxim Ryskov
04:15:48
все будет 👍 ща придет
Егор Городецкий
04:16:02
Решаем 7 задачу
skimono (Камиль Шайхразиев)
04:16:18
Я хз, как её передать преподу
skimono (Камиль Шайхразиев)
04:16:23
Мб в доту?
Илья Резник
04:16:51
Так и свергли Николая
Kiraashado(Егор Бородатов)
04:17:01
Он улетел
Ришат Хайруллин
04:17:03
теперь ты ведёшь урок
Kiraashado(Егор Бородатов)
04:17:06
Но обещал вернуться
Ришат Хайруллин
04:17:08
поздравляю
Арсений Строков
04:17:24
Рассказывай решение 7, че тупишь
Егор Городецкий
04:17:31
Смотри
Руслан
04:17:48
Камиль рассказывай 7 задачу
Руслан
04:18:01
а вот все
Егор Городецкий
04:18:22
А будет 4D-Мо?
я не Ашим, а Миша
04:18:32
не надо
Руслан
04:18:34
а 100D как в кинотеатрах?
Хамитов Хаким
04:18:36
может сразу 5D
Егор Городецкий
04:18:41
SD
Вячеслав Рощин
04:18:43
да
Константин Белоусько
04:18:44
чтобы его сокращённо называть 4МО?
Михаил Данилов
04:18:44
может сразу XD
Арсений Строков
04:18:49
капец круто
Николай Федоров
04:19:18
для массива МО и фенвик
Никита Гребень
04:19:26
будем для каждого числа поддерживать количество вхождений через до и тривиально обрабатывать в мо
Николай Федоров
04:19:39
фенвик никита
Вячеслав Рощин
04:19:43
KD Мо?
Никита Чистяков
04:19:44
фенвик + дд ы
Никита Гребень
04:19:45
до снизу коля
Maxim Ryskov
04:20:08
никто не юзает фенвик
а
04:20:14
эээ
а
04:20:16
всмысле никто
Вячеслав Рощин
04:20:19
+
skimono (Камиль Шайхразиев)
04:20:20
Осуждаю
Вячеслав Рощин
04:20:27
Фенвика?
Kiraashado(Егор Бородатов)
04:21:49
Я то же самое сказал же(Ладно
Арсений Строков
04:21:52
Настоящие джентельмены тут дд пишут
skimono (Камиль Шайхразиев)
04:21:59
Фуу
а
04:22:01
нет..
Maxim Ryskov
04:22:03
пхахахаха
Руслан
04:22:06
но….
Хамитов Хаким
04:22:07
n * sqrt(n) * log n?
Константин Белоусько
04:22:08
настоящие джентльмены не пишут дд
Kiraashado(Егор Бородатов)
04:22:11
Да
а
04:22:20
🍉
Балабекян Андрей
04:22:44
typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;// типа написал ДД
Руслан
04:22:52
треш
Антон Мартынов
04:23:16
там еще инклуды какие-то и using namespace
Антон Мартынов
04:23:25
для ordered_set
Балабекян Андрей
04:23:30
#include <bits/extc++.h> вместо битсов
Хамитов Хаким
04:23:33
ТРЭШ
Балабекян Андрей
04:23:47
И using namespace __gnu_pbds
а
04:24:12
и не компилится потом локально
Николай Федоров
04:24:27
дерево фенвика работает за 1
Вячеслав Рощин
04:24:34
Можно ещё раз как мы дерево к МО свели?
Хамитов Хаким
04:24:44
это ассимптотика для всех запросов?
Вячеслав Рощин
04:24:44
А,тогда жду
Николай Федоров
04:24:51
но там же в корневой и запрос и изменение за корень, то есть нет разницы
Kirill Stepnov
04:25:03
а если q != n то какая асимптотика будет ?
Kirill Stepnov
04:25:19
хорошо
Янко Анастасия
04:25:36
Как мы ДО к Мо свели?
Хамитов Хаким
04:25:37
для полного решения нужен массив посещения вершин дерева?
я не Ашим, а Миша
04:25:57
эйлеров обход?
Хамитов Хаким
04:26:04
lf
Хамитов Хаким
04:26:07
да
Хамитов Хаким
04:26:19
я это имел ввиду
я не Ашим, а Миша
04:27:10
тогда уж больше 1 раза
Хамитов Хаким
04:27:32
а если эйлеров нельзя построить?
Хамитов Хаким
04:27:52
это точно эйлеров?
Николай Федоров
04:27:54
а это решается эйлеровым обходом?
Константин Белоусько
04:28:15
1213141?
Хамитов Хаким
04:28:33
надо короче МО с фенвиком на отрезке
я не Ашим, а Миша
04:28:37
1221331441
Хамитов Хаким
04:29:07
это разве называется эйлеров обход?
Николай Федоров
04:29:09
непонятно как пользоваться тем, что вершины, которые не лежат на пути встречаются четное количество раз в этой задач
я не Ашим, а Миша
04:29:10
(
Николай Федоров
04:29:26
а как его не учитывать?
Николай Федоров
04:29:27
здесь
Хамитов Хаким
04:29:33
там же надо по каждому ребру 1 раз пройтись?
Хамитов Хаким
04:29:39
в эйлеровом
Хамитов Хаким
04:30:10
я тоже понял
Хамитов Хаким
04:31:11
это эта штука для lca за 1 надо
Хамитов Хаким
04:31:15
?
skimono (Камиль Шайхразиев)
04:31:21
да
Хамитов Хаким
04:31:31
👍🏻
я не Ашим, а Миша
04:31:55
может до другое?
Хамитов Хаким
04:32:12
а там что ли на ребрах числа?
Хамитов Хаким
04:32:21
ок
я не Ашим, а Миша
04:33:14
пройти до lca и спуститься?
я не Ашим, а Миша
04:34:17
чтобы перейти из одной вер до другой
я не Ашим, а Миша
04:34:27
а мо по эйлеровому
Арсений Строков
04:34:30
удалили 2 нужных(
Хамитов Хаким
04:34:38
золотой маркер)
Антон Мартынов
04:35:24
Может тогда отсортировать сначала по блоку позиции L в эйлеровом обходе, потом по положению R в эйлеровом обходе.
я не Ашим, а Миша
04:35:28
мо по эйлеру
Хамитов Хаким
04:36:12
Мо по эйлеровому с фенвиком?
Хамитов Хаким
04:36:20
или с до
Янко Анастасия
04:36:26
То есть мы сортируем запросы в порядке обхода дерева?
Хамитов Хаким
04:36:33
да
Kirill Stepnov
04:36:38
то есть вся разница в том что у нас теперь массивом будут являтся вершины в порядке эйлерова обхода ?
Антон Мартынов
04:36:42
да
Телелюхин Артём
04:37:02
А какой из Эйлеровых обходов?
Вячеслав Рощин
04:37:06
+
Хамитов Хаким
04:37:16
полный короче
Maxim Ryskov
04:37:23
то есть у нас мо по неявному эйлерову типо того да?
Константин Белоусько
04:37:33
почему по неявному?
Хамитов Хаким
04:37:36
по я вному вроде
Maxim Ryskov
04:37:46
то есть эйлеров нужен ток для сорта отрезков, а ответ ищем по самому дереву без эйлерова?
Хамитов Хаким
04:38:07
с эйлеровым
Maxim Ryskov
04:38:09
все кайф
Хамитов Хаким
04:38:31
ой
Телелюхин Артём
04:39:10
Как при сортировке понять, какой запрос раньше/позже, если у одной вершины несколько индексов в Эйлеровом обходе?
Хамитов Хаким
04:39:19
первый
Телелюхин Артём
04:39:35
Почему?
я не Ашим, а Миша
04:39:55
задача будет?
Вячеслав Рощин
04:39:59
есть
Вячеслав Рощин
04:40:03
MEX на пути
Руслан
04:40:09
а через сколько мы заканчиваем примерно?
я не Ашим, а Миша
04:40:12
спасибо
Maxim Ryskov
04:40:28
кажется уже все разобрали
Арсений Строков
04:40:38
примерно через 15 минут 43 секунды
Никита Гребень
04:41:25
это правда что чтоб ходить по дереву нужно писать бин подъемы?
Вячеслав Рощин
04:41:33
скорее всего
Вячеслав Рощин
04:41:42
т.к как ты поймёшь куда двигаться то надо чтобы попасть в вершину
я не Ашим, а Миша
04:41:46
lca думаю
Никита Гребень
04:42:14
меня кокнуло
Вячеслав Рощин
04:42:20
Ещё даже не конец
Maxim Ryskov
04:42:38
нужно lca
я не Ашим, а Миша
04:43:12
спасибо, до свидания
Константин Белоусько
04:43:28
до свидания
Хамитов Хаким
04:43:28
го какой-нибудь прикольный цвет
Михаил Данилов
04:43:37
очень юзефул, спасибо
Михаил Данилов
04:44:05
серьезно, если что*
Янко Анастасия
04:44:19
Можно ещё про асимптотику в этой задаче поговорить?
Никита Гребень
04:44:31
спасибо за лекцию
Хамитов Хаким
04:44:46
Всем пока!
Maxim Ryskov
04:45:13
лекция огонь, всем до встречи!
10В Галявиев Арслан
04:45:32
бб
Карим Мотыгуллин
04:45:34
спасибо лекцию, мегасочно
zitraks
04:46:30
бб
Янко Анастасия
04:53:16
Что такое k?
Балабекян Андрей
04:53:40
Количество запросов в данной паре блоков
Янко Анастасия
04:54:33
Можно ещё раз про пару блоков?
Янко Анастасия
04:55:06
Ладно
Никита Чистяков
04:56:28
у нас приоритеты сортировки такие же ? : 1) l/sqrt 2) r 3) q
skimono (Камиль Шайхразиев)
04:56:44
Вроде да
Михаил
04:57:53
r / sqrt
Михаил
04:58:42
не sqrt кстати
Kirill Stepnov
05:02:52
у меня есть вопрос не по теме леции (хочу спросить некоторый совет), я могу его тебе в личные сообщения задать ?
Телелюхин Артём
05:03:03
Как искать MEX на пути? Хотя бы идею
Kirill Stepnov
05:03:09
хорошо
Егор Кол…
05:03:23
Спасибо за лекцию!!!)
Михаил
05:04:04
Спасибо!
Янко Анастасия
05:07:16
Как в задаче на поиск количества инверсий на пути делить обход дерева на блоки для сортировки?
Янко Анастасия
05:08:32
Как запросы сортировать?
Балабекян Андрей
05:08:58
Спасибо большое, очень классная лекция, отлично объясняете!
Влад Романовский
05:09:30
Спасибо, лектор топ)
skimono (Камиль Шайхразиев)
05:09:50
Спасибо за лекцию, до свидания
Телелюхин Артём
05:11:00
Как искать MEX на пути? Хотя бы идею
Янко Анастасия
05:11:02
Лекция шикарна, спасибо!
Вячеслав Рощин
05:11:14
+, всем бб
Телелюхин Артём
05:11:38
Ок
Даша Жилина
05:12:06
Всего то 2 часа ночи