RuCode 6.0 Final CD: двумерный тернарный поиск, неправильная жадность и Rope в задачах для гурманов!

Мы вернулись с двумерным тернарным поиском и его оптимизациями, методом золотого сечения, авто-векторизацией, оптимизациями компилятора (прагмами), правильными и неправильными жадниками и структурами данных, которые могут вырезать и вставлять подстроки за логарифм! Вооружайтесь тайм-кодами, исходниками, и врубайте скорость х2!

Мой логин: rucode6-team-1034
Мой пароль: ztZxX7D5RN

00:00:00 Разговариваем о VK Cup 2022
00:06:00 Задача E. Effective Transmission
00:10:00 Уравнение эллипса
00:11:15 Поворот плоскости в комплексных числах
00:16:00 Второй способ: матрицы поворота
00:18:30 Масштабирование по оси Ох
00:23:20 Свели к окружности минимального радиуса
00:27:10 Окружности мин. радиуса - единственная
00:29:00 Радиус для заданного центра
00:30:50 Численные методы, сходящиеся к ответу
00:33:50 Тернарный поиск: одномерный
00:39:10 Ускорение тернарного поиска: неравные отрезки
00:46:33 Двумерный тернарный поиск
00:49:10 Исходный код на плюсах
00:55:45 Зачем прагмы? Получаем TL без них
00:58:15 Параметры оптимизации исходного кода
01:04:04 Выворачиваем циклы (unroll-loops)
01:08:30 256-битные регистры YMM для векторизации AVX
01:09:40 Покомпонентные операции над регистрами (SIMD)
01:12:40 Авто-векторизуем цикл!
01:15:00 Покомпонентный максимум
01:18:00 Разница между AVX и AVX2, AVX512F, SSE4.1, SSE4.2
01:21:20 Какие процессоры поддерживают AVX?
01:23:50 Неэффективность AVX512, нагрев и снижение частоты процессора
01:26:45 Ключевое слово __restrict - нужно или нет?
01:37:00 Сделали 12 млрд операций за 1.3 секунды
01:38:30 Просто уменьшаем количество итераций - вместо шаманства с AVX
01:40:00 Получаем 0.9 секунд с 75 итерациями
01:40:25 Меняем длины отрезков и получаем 0.4 секунды
01:43:30 Метод золотого сечения: уменьшаем количество вызовов функции
01:49:00 Задача J. Jewels of Ice and Fire
02:06:00 Контрим жадник у Данила
02:09:00 Проще всего написать стресс-тест...
02:17:55 Задача M. Memory Test
02:23:00 Какие операции над строками нужны?
02:25:30 Как быстро дублировать цикл?
02:28:28 Структура данных __gnu_cxx::rope (rope, цепочка)
02:32:30 Исходный код на плюсах
02:38:20 Контрим Сармата. Слабые тесты
02:50:00 Прощаемся

[cp_mirea]

Мы вернулись? А мы никуда и не уходили. Мы просто слишком долго превращали эллипс в окружность... Вооружайтесь тайм-кодами и врубайте скорость х2!
00:00:00 Разговариваем о VK Cup 2022
00:06:00 Задача E. Effective Transmission
00:10:00 Уравнение эллипса
00:11:15 Поворот плоскости в комплексных числах
00:16:00 Второй способ: матрицы поворота
00:18:30 Масштабирование по оси Ох
00:23:20 Свели к окружности минимального радиуса
00:27:10 Окружности мин. радиуса - единственная
00:29:00 Радиус для заданного центра
00:30:50 Численные методы, сходящиеся к ответу
00:33:50 Тернарный поиск: одномерный
00:39:10 Ускорение тернарного поиска: неравные отрезки
00:46:33 Двумерный тернарный поиск
00:49:10 Исходный код на плюсах
00:55:45 Зачем прагмы? Получаем TL без них
00:58:15 Параметры оптимизации исходного кода
01:04:04 Выворачиваем циклы (unroll-loops)
01:08:30 256-битные регистры YMM для векторизации AVX
01:09:40 Покомпонентные операции над регистрами (SIMD)
01:12:40 Авто-векторизуем цикл!
01:15:00 Покомпонентный максимум
01:18:00 Разница между AVX и AVX2, AVX512F, SSE4.1, SSE4.2
01:21:20 Какие процессоры поддерживают AVX?
01:23:50 Неэффективность AVX512, нагрев и снижение частоты процессора
01:26:45 Ключевое слово __restrict - нужно или нет?
01:37:00 Сделали 12 млрд операций за 1.3 секунды
01:38:30 Просто уменьшаем количество итераций - вместо шаманства с AVX
01:40:00 Получаем 0.9 секунд с 75 итерациями
01:40:25 Меняем длины отрезков и получаем 0.4 секунды
01:43:30 Метод золотого сечения: уменьшаем количество вызовов функции
01:49:00 Задача J. Jewels of Ice and Fire
02:06:00 Контрим жадник у Данила
02:09:00 Проще всего написать стресс-тест...
02:17:55 Задача M. Memory Test
02:23:00 Какие операции над строками нужны?
02:25:30 Как быстро дублировать цикл?
02:28:28 Структура данных __gnu_cxx::rope (rope, цепочка)
02:32:30 Исходный код на плюсах
02:38:20 Контрим Сармата. Слабые тесты
02:50:00 Прощаемся