[Logo] Форум DL
  [DL]  На главную страницу 
Индекс форума ->Олимпиадное программирование ->Методика подготовки к IOI 2007 - ... 1, 2, 3, 4
Автор Сообщение
Михаил Долинский

Темы: 1982
Сообщений: 47186

Мой профиль
Общие идеи (c Codeforces)
Александр Кульков, Украина, Запорожье из организации МФТИ сделал
подборку идей, которые могут быть применены к достаточно большому классу задач.
Почитать - вдруг есть что-то полезное.
В ближайшую среду обсудим непонятое, если будут желающие.
4 7 8 9 12 14 18

http://dl.gsu.by/images/solutions/solutions_1823028_eHzwh_1545724071719.pdf



Educational rounds
Бирич, Гацуков, Ермаков, Костяной, Харрасов
– просматривают, выбирают интересные задачи: ДП, сложные структуры данных, графы, теория чисел, другое
(есть смысл по темам, один берёт ДП, другой, ССД, третий – графы, 4 – теория чисел, 5 - другое)
Систематизируют, думаем, что с ними дальше сделать
Варианты
- докладчик по теме рассказывает «теорию» для этих задач (предварительно подготовив конспект со ссылками)
- желающие сдают на Codeforces
- желающие ставят аналоги на DL – для последующих олимпиад

Есть ещё вариант
К объявленной теме пытаются придумать решение/понять описание все.
Обсуждается то что кем-то не понято.

Надо разбирать все задачи, или только те, на которые укажет ответственный по теме?

В общем как с этим материалом лучше работать ещё предстоит придумать и улучшить практикой.


Слава Ермаков:

Ермаков - ССД
Костяной - Строковые структуры
Бирич - ДП
Гацуков - Графы
Харрасов - Теория чисел 



13 января 2019:

Ермаков - ССД, ДП
Костяной - Строковые структуры, графы
Харрасов - Теория чисел(2) 



17 апреля 2019:


Харрасов - ССД, ДП
Костяной - Строковые структуры, графы 



19 января 2020:


Харрасов - ССД
Костяной - Строковые структуры
Попович - Графы
Лосев - ДП
Горбатовский - ДП,
Ситников - элементы теории чисел
 



#539 Div.1 E. Саша и очень лёгкий тест дерево отрезков, факторизация
#560 Div.3 E. Два массива и сумма функций жадный, математика, сортировка
Михаил Долинский

Темы: 1982
Сообщений: 47186

Мой профиль
ECR – Educational Codeforces Round,
ссылка на разбор раунда, ссылка на условие задачи (с возможностью сдать решение)

Сложные структуры данных - Харрасов [Ермаков]

#152 F. XOR-разделение двоичный бор
#152 E. Максимум справа от минимума монотонный стек
#150 E. Заполни матрицу - С++ map
#149 F. Разбор на двоих - двусвязный список, дихотомия
#141 G. Радиус взвешенного дерева дерево отрезков на запросах, ДП на графе, DCP(dynamic connectivity problem), LCA - двоичные подъёмы или Sparse Table на Эйлеровом обходе(брать LCA за O(1))
#140 F. Два поддерева SQRT-декомпозиция, эйлеров обход дерева
#138 F. Расстояние до пути дерево Фенвика, ДП на графе, LCA, двоичный подъём
#137 F. Пересечение и объединение дерево отрезков-лист матрица 2*2, contributon to the sum, ДП
#135 C. Цифровой логарифм C++ priority_queue
#134 E. Запросы про префикс функцию префикс-функция, конечный автомат
#134 D. Максимальное И C++ map, битовая обработка, маски
#133 E. Обмен и максимальный отрезок дерево отрезков
#132 F. Мультимножество строк двоичный бор, ДП на дереве, FFT
#132 D. Роророробот разреженная таблица для RMQ
#131 F. Точки дерево отрезков
#124 F. Tower Defense персистентное дерево отрезков
#123 D. Раскраска крестиками C++ Set
#120 F. Квадратное множество хеш составного равен XOR хешей простых делителей, C++ Map
#116 F. Древесные запросы метод обработки событий, дерево Фенвика или дерево отрезков по Эйлерову обходу дерева
#112 F. Хороший граф дерево Фенвика (BIT) построенный на эйлеровом обходе дерева: она может прибавлять значение в ребро и брать сумму на пути от вершины v к корню
#112 E. Скучные отрезки дерево отрезков
#107 G. Фишки на доске дерево Фенвика/дерево отрезков
#105 E. A-Z граф два сета с парами
#104 E. Дешевый обед ДП+структура данных(добавлять,удалять,брать минимум,поддерживать дубликаты)
#103 G. Минимальная разница SQRT-декомпозиция (алгоритм Мо)
#103 F. Фонари дерево отрезков(минимум), ДП
#101 F. Розетки дерево отрезков (прибавлять на отрезке, брать значение в точке и искать самый короткий префикс с суммой хотя бы k), дерево, жадный
#99 G. Запрещенное значение ДП, С++ set, C++ map, small-to-large
#95 G. Три вхождения дерево отрезков (минимум на отрезке, количество минимумов на отрезке)
#95 D. Мусорная задача Мультимножество
#93 E. Два типа заклинаний С++ Set
#91 F. Странное сложение дерево отрезков
#90 G. Пешки дерево отрезков с отложенными вычислениями
#85 F. Странная функция дерево Фенвика, ДП
#82 F. Количество компонент DSU
#81 E. Разделение перестановки дерево отрезков (прибавить на отрезке, минимум на отрезке)
#80 E. Симулятор мессенджера что угодно: дерево отрезков с векторами в вершинах, Мо, персистентное дерево отрезков
#78 C. Ягодное варенье map C++
#78 D. Дерево отрезков set C++, DSU
#78 E. Тесты для задачи D small-to-large
#75 E2. Голосование (усложнённая версия) multiset C++
#73 F. Выбери квадрат дерево отрезков, сжатие координат
#72 E. Запросы суммы? ДО влияние кеш-памяти компа
#71 F. Задача об остатках SQRT-декомпозиция
Михаил Долинский

Темы: 1982
Сообщений: 47186

Мой профиль
#69 E. Культурный код ДО(минимум, количество минимумов + ДП)
#68 E. Посчитайте четырехугольники Дерево Фенвика, декремент/инкремент на 1, сумма на отрезке
#67 D. Сортировка подотрезков дерево отрезков
#66 G. Очередная задача на разбиения "Convex hull trick и персистентное Li Chao tree" или Divide-and-Conquer
#66 E. Минимальное покрытие отрезков "двоичные подъёмы" или "сжатие пути"
#66 D. Разделение массива суффиксные суммы
#65 G. Малобюджетное Начало bitset
#65 F. Скалярные запросы Дерево Фенвика
#64 E. Специальные подотрезки перестановки логарифмической структуры данных, или двумя проходами по массиву со стеком
#62 F. Расширение множества точек СНМ, дерево отрезков
#62 C. Плейлист C++ set
#61 G. Жадные подпоследовательности Дерево Отрезков по Эйлеровому обходу дерева
#61 D. Напряженная тренировка куча событий и заменяющий её массив
#60 G. Рекурсивные запросы BIT или итеративное ДО
#59 G. Вася и максимальный заработок Дерево отрезков и С++ set
#56 E. Пересечение перестановок n деревьев Фенвика, каждое с дерамидой внутри (ordered_set шаблона из pbds обычно достаточно)
#56 G. Многомерные запросы дерево отрезков над каждым массивом
#55 E. Увеличение частоты найти подотрезок максимальной суммы
#51 G. Дистинктификация
Нам понадобятся:
• DSU;
• Какая-нибудь неявная логарифмическая структура данных (нам понадобятся операции «посчитать сумму элементов меньше x» и «посчитать количество элементов больше y», или какие-нибудь другие подобные операции);
• Слияние при помощи метода small-to-large.
#47 F. Доминирующие индексы слияние массивов глубин
#46 C. Подсчет покрытых точек сжатие координат
#46 F. Одно вхождение персистентное ДО | обычное ДО | алгоритм Мо
#41 E. Туфурама поддерживать единицы и нули в BIT #39 G. Почти возрастающий массив два дерева отрезков с откатами
#37 F. SUM и REPLACE два дерева отрезков (сумма, максимум)
#36 E. Занятия физкультуры сет
#35 G. Запросы на массовое обновление сканирующая прямая, дерево отрезков
#34 D. Почти разница map/hashmap
#31 E. Бинарная матрица DSU
#30 E. Награждение победителей Максимум на отрезке: дерево отрезков | sparse table | квадратной матрицей за O(n2) предпросчета и O(n2) памяти
#29 D. Очередная задача про запросы в массиве декартово дерево
#26 G. Функции на отрезках персистентное ДО
#23 D. Несбалансированный массив стек
#23 F. Запросы на MEX декартово дерево | дерево отрезков | корневая декомпозиция
#22 E. Создание армии дерево отрезков #20 G. Периодическая задача RMQ сжатие координат+ДО | sparse table + неявное ДО
#19 E. Запросы на массиве Объединение решений
#17 E. Радиостанции fenwick tree
#13 F. Лена и запросы SQRT-декомпозиция
#10 D. Вложенные отрезки стандартная двумерная задача, которая решается с помощью одномерной структуры данных
#6 D. Профессор GukiZ и два массива map+lower_bound
#6 F. Ксоры на подотрезке алгоритмом Мо + 2 бора
#3 F. Лягушки и комары динамическое дерево отрезков
Михаил Долинский

Темы: 1982
Сообщений: 47186

Мой профиль
Строковые структуры и ДП - Костяной

#149 C. Лучшая двоичная строка ДП по строкам
#147 E. Переставь скобки ДП по строкам
#140 C. Посчитайте бинарные строки ДП по строкам
#137 G. Антифибоначчиевый разрез ДП по строке
#136 E. Робот-пылесос ДП по строке, алгороим Ахо-Карасика, битмаски
#136 C. Карточная игра ДП по строке
#135 D. Выбор букв ДП по строке, стратегические игры
#119 G. Подпоследовательности повсюду ДП по строкам, ДП по маскам, SOS DP, преобразование Мёбиуса
#115 G. Сумма хороших чисел хеши по строкам
#115 F. ПСП ДП на строках, по маскам
#110 F. Расстояние между строками классы эквивалентности, ДП на строках
#107 F. Чайнворд бор, ДП, возведение матрицы в степень
#106 E. Хаотичное слияние ДП на строках
#99 F. Строка и операции ДП на строках
#98 C. Две скобки стек
#97 G. СУБД смерти алгоритм Ахо-Карасика или хеши или суффиксная структура
#96 E. Переворот строки дерево Фенвика - подсчёт количества инверсий
#94 F. x-простые подстроки ДП по строке
#93 F. Спорные раунды ДП по строке
#89 G. Построй строку ДП по строке
#85 G. Поиск подстроки префикс-функция, FFT
#84 G. Буквы и знаки вопроса автомат Ахо-Корасик на массиве строк, ДП по строке и бит-маске
#83 G. Автодополнение бор, ДП, дерево отрезков
#82 E. Удаляем подпоследовательности ДП
#82 C. Идеальная клавиатура
#81 B. Бесконечные префиксы
#81 C. Получи строку
#79 F. Новый год и смена хендла "lambda-optimization" i.?e. "aliens trick".
#78 A. Хеширование перемешиванием
#74 C. Обычная условно-бесплатная игра
#74 D. AB-строка
#71 G. Инди альбом автомат Ахо-Корасик
#70 F. Вам заданы буквы...
#70 E. Вам задана строка... корневая эвристика, бор
#70 D. Выведите 1337-строку...
#70 C. Вам задана WASD-строка...
#70 B. Вам задана десятичная строка
#65 D. Двухцветная ПСП баланс скобок
#63 A. Разверни подстроку
#61 F. Удали строку ДП
#61 A. Правильная скобочная последовательность
#60 F. Аккуратная строка ДП по битмаскам
#60 E. Расшифруй строку
#59 E. Вася и двоичная строка ДП
#59 C. Brutality два указателя и сортировки
#58 B. Баян
#57 D. Простая задача
#55 F. Быстрый набор
#53 G. Очередная задача на строки (Yet Another LCP Problem) Суффиксный Массив + линейное LCP + Sparse Table
#52 E. Преобразования краев
#52 G. Суффиксы Фибоначчи
Михаил Долинский

Темы: 1982
Сообщений: 47186

Мой профиль
#47 G. Разрешенные буквы теорема Холла
#45 C. Конкатенация скобочных последовательностей
#44 F. Изоморфные строки хэши
#41 F. K-подстроки хэш | суффиксный массив
#40 I. И снова равные строки битсеты | (скрытый граф + FFT)
#39 F. Фибоначчиевы подпоследовательности перемножение матриц автоматов по КМП
#38 F. Удаляем подстроки ДП по битмаскам
#34 E. Обмены в строке
#31 F. Распалиндруй! поток минимальной стоимости | жадный алгоритм
#30 B. Сбалансированная подстрока
#30 F. Запрещённые индексы суффиксный массив
#25 D. Подходящая замена бинпоиск по ответу, жадное восстановление ответа
#25 F. Сжатие строки префикс-функция
#23 E. Выбор командира двоичный бор
#21 G. Гимн Берляндии префикс-функция, КМП, ДП по строке

#19 C. Минимальная строка стек
#18 C. Поделись на три!
#17 C. Две строки два указателя
#16 E. Генерация строки ДП на строках
#16 F. Операции над множеством строк алгоритм Ахо-Корасика
#12 C. Простые строки жадный | ДП на строках
#12 E. Красивые подмассивы битовый бор
#9 C. Наименьшая конкатенация строк
#8 C. Медведь и расстояние между строками жадный
#8 E. Zbazi в Zeydabad дерево Фенвика
#5 F. Дорогие строки суффиксный автомат | суффиксное дерево
#4 C. Заменить до правильной скобочной последовательности стек
#2 C. Сделай палиндром
Михаил Долинский

Темы: 1982
Сообщений: 47186

Мой профиль
.
Михаил Долинский

Темы: 1982
Сообщений: 47186

Мой профиль
ДП - Лосев, [Харрасов, Ермаков, Бирич]

#151 E. Коробки и шары ДП по 3 параметрам
#148 F. Зомби exchange argument DP, оптимизации «разделяй и властвуй» и aliens trick
#148 E. Задачка на комбинаторику - ДП - префиксные суммы
#147 F. Древесина - производящие функции
#146 E. Фишки на цепочке - ДП на графе, техника "Contribution to the Sum"
#145 G. Прогноз количество перестановок
#143 G. Последовательные удаления ДП на ациклическом графе, обработка блоками по 64 вершины, битсеты
#143 E. Взрывы? ДП по одному параметру
#143 C. Дегустация чая префиксные суммы, разностный массив, двоичный поиск
#142 F1. Покраска графа (простая версия) ДП, граф, комбинаторика
#141 D. Различные массивы ДП по 2 параметрам
#140 E. Algebra Flash скрытый граф, ДП на графе по битмаскам
#139 E. Декомпозиция ДП от двух параметров
#137 E. FTL ДП от одного параметров
#136 E. Робот-пылесос ДП от трёх параметров
#135 G. Освещение метод включения-исключения, подмаски, sum-over-subsets
#133 F. Мешки с шарами ДП по 2 параметрам, «contribution to the sum»
#133 D. Перемещение фишки ДП по 2 параметрам
#130 E. Раскраска скрытый граф, ДП на дереве
#129 F. Уникальные вхождения ДП на дереве, "contribution to the sum" или динамическая связность
#129 E. Приключения в лабиринте ДП (аналогично двоичному подъёму), или дерево отрезков, разделяй и властвуй по запросам, корневая декомпозиция
#127 F. Подсчет перестановок ДП по 4 параметрам, метод Berlekamp-Messey анализа рекуррентных последовательностей
#127 E. Прямой обход ДП на дереве, классы эквивалентности
#125 F. Слова на дереве 2-SAT, LCA
#125 E. Минимальная покрывающая звездочка ДП на графе
#125 D. Для геймеров. От геймеров. префиксные суммы
#122 D. Сделай равными ДП (рюкзак)
#119 F. Двудольный массив ДП по 3 параметрам
#118 F. Раскраска дерева формула включений-исключений, ДП по 2 параметрам, FFT-ускорение, разделяй и властвуй
#117 F. Доспехи и оружие скрытый граф, ДП-кратчайшие пути, BFS
#116 E. Арена ДП по 2 параметрам
#114 F. Вхождения скрытый граф, ДП
#113 F. Палиндромный гамильтонов путь ДП по битмаске, хеширование состояний в число в 6-ричной системе счисления
#111 E. Stringforces ДП по битмаскам вместо перебора перестановок
#109 D. Кресла ДП по 2 параметрам
#108 D. Максимальная сумма произведений префиксные суммы
#108 C. Берляндский отбор префиксные суммы
#106 F. Разрезы диаметров ДП на дереве
#106 E. Хаотичное слияние ДП на строках
#104 G. Подсчет строк ДП по строке
#104 F. Единицы ДП по числу
#100 F. Максимальное правильное множество ДП по битмаскам
Михаил Долинский

Темы: 1982
Сообщений: 47186

Мой профиль
#97 F. Эмоциональные рыбаки ДП по 2 параметрам
#97 C. Шеф Монокарп ДП по 2 параметрам
#96 G. Очередное взвешивание графа ДП на дереве, по профилю, по битмаскам
#96 F. Реалистичный геймплей
#94 G. Наемники метод включений-исключений
#94 E. Очистите мультимножество ДП по двум параметрам
#93 D. Цветные прямоугольники ДП по трём параметрам
#92 G. Выбираем направления скрытый граф, ДП на дереве
#90 D. Максимальная сумма на четных позициях ДП применить какую-то функцию только к небольшому количеству подмассивов
#89 F. Прогулка по графу ДП на графе,выпуклая оболочка, арифметическая прогрессия
#88 D. Очередная очередная задача алгоритм Kadane
#87 F. Призыв существ ДП или венгерский алгоритм решения задачи о назначениях или потоки минимальной стоимости
#87 E. Раскраска графа ДП на дереве
#86 F. Сделай возрастающим ДП по битмаскам
#86 E. Расстановка ладей метод включения-исключения
#84 F. Отрезки И по каждому биту отдельно
#83 E. Сжатие массива префиксная динамика
#81 F. Хороший контест
#79 E. Новогодние перестановки лексикографическое восстановление ответа
#78 F. Карты мат.ожидание
#77 F. Покрашенное дерево ДП на графе
#77 E. Турнир
#74 E. Покупка клавиатуры ДП по подмножествам
#74 F. Максимальное поддерево ДП на графе
#73 D. Сделаем забор великим снова
#69 F. Игра с раскрашиванием игры, функция Гранди, матрицы
#68 G. Очередная мемная задача цифровая динамика (ДП по числу) на 7-мерном массиве - или состояния обозначаются специальными структурами, и эти структуры хранятся в map
#67 E. Покраска дерева ДП по поддереву, переподвешивание деревьев
#64 F. Мешок с карточками вероятность
#63 F. Олигополия на доставку ДП на графе с битмасками
#63 D. Красивый массив
#61 E. Рюкзак
#61 C. Покраска забора префиксные суммы #59 F. Вася и бесконечные кредиты Венгерский алгоритм
#58 F. Грузовики и города
#57 E. Супер-Бомбардир
#56 F. Вася и массив
#55 C. Мультипредметная олимпиада
#54 F. Отчет по летней практике
#54 G. Игра на массиве
#53 E. Segment sum (Сумма на отрезке) - ДП по числу
#51 D. Двураскраски
#51 E. Вася и длинные числа - ДП по числу
#50 C. Шикарные числа - ДП по числу
#49 E. Противоположная раскраска
#46 D. Очередная задача на подпоследовательности
#44 E. Коробки с карандашами
#40 F. Задача о бегуне ДП+возведение матрицы в степень
#39 D. Расписание
#34 F. Замена подматриц ДП по изломанному профилю
#32 F. Соедини вершины
Михаил Долинский

Темы: 1982
Сообщений: 47186

Мой профиль
Графы - Попович [Костяной]

#147 E. Переставь скобки скрытый граф, жадный
#146 F. Вышки связи задача о динамической связности оффлайн
#145 F. Путешествие по Берляндии двоичные прыжки
#143 F. Блокирующие фишки жадный на дереве
#141 F. Двойная сортировка II скрытый граф, максимальное паросочетание
#139 F. MCF поток минимальной стоимости
#138 E. Кактусовая стена скрытый граф, кратчайший путь Дейкстрой или 0-1 BFS
#136 D. Сбросить k ребер дерево, жадный, стек
#135 F. Рыбаки максимальное паросочетание, оптимизированный алгоритм Куна
#134 F. Уменьшение паросочетания максимальное паросочетание, алгоритм Куна или Диница
#132 E. XOR дерево lca, small-to-large
#130 F. Слишком много ограничений скрытый граф, 2-SAT
#126 E. Узкие компоненты скрытый граф, СНМ
#124 E. Сумма паросочетаний Максимальное паросочетание
#122 F. Совершенное паросочетание Link/Cut Tree или Heavy-Light декомпозиция + дерево отрезков с поддержанием отложенных вычислений
#122 E. Запросы об остовном дереве Мин.Ост.Дер. Крускал
#111 F. Попрыгунчик скрытый граф, алгоритм Борувки для мин.ост.дерева ~ N*((LogN)^2)
#110 E. Поставки золота двоичный подъём
#109 F. Гоблины и гномы максимальное паросочетание, ДП на графе
#108 F. Сундуки и ключи скрытый граф, максимальный поток
#108 E. Сдвиг на один скрытый граф, максимальное количество смежных пар ребер
#107 D. Строка минимальной стоимости скрытый граф, эйлеров цикл
#106 G. Раскраска графа граф + 2 дека + слияние small-to-large ИЛИ декартово дерево по неявному ключу
#105 F. Уничтожение ребер скрытый граф, эйлеров путь
#105 D. Dogeforces дерево, DFS
#103 E. Сопоставление шаблонов скрытый граф, топологическая сортировка
#102 F. Странное множество минимальный разрез в потоковой сети
#102 E. Минимальный путь скрытый граф, Дейкстра
#100 E. План лекций топологическая сортировка
#98 G. Игра на дереве центроидная декомпозиция
#97 D. Дерево минимальной высоты дерево, BFS, жадный
#97 C. Шеф Монокарп наибольшее паросочетание минимальной стоимости. MCMF или Венгерский алгоритм
#92 F. Двухцветные отрезки скрытый граф, независимое множество, максимальное паросочетание
#91 E. Слияние башен LCA
Михаил Долинский

Темы: 1982
Сообщений: 47186

Мой профиль
#85 E. Пути по делителям кратчайшие пути, GCD
#84 D. Бесконечный путь циклы, GCD
#82 G. Сумма префиксных сумм центроидная декомпозиция, выпуклая оболочка или дерево Li Chao.
#80 F. Красно-синий граф - потоки - flows with demands
#73 G. Граф и числа метод включения-исключения
#72 F. Задача с обязательными онлайн-запросами Dynamic Connectivity Problem, корневая эвристика, СНМ
#72 D. Покраска ребер
#67 G. Сходка поток минимальной стоимости
#65 C. Распространение новостей скрытый граф, компоненты связности и их размеры, DFS или СНМ
#64 G. Оптимизатор скрытый граф
#64 D. 0-1-Дерево СНМ
#62 G. Двойное дерево двоичный подъем или центроидная декомпозиция
#58 D. Подсчёт GCD
#56 D. Красивый граф
#55 D. Граф максимального диаметра
#55 G. Петя и граф
#54 D. Удаление ребер
#54 E. Вася и дерево
#53 F. Выбери два пути центр дерева принадлежит всем диаметрам этого дерева
#52 B. Вася и изолированные вершины
#52 D. Три фигуры
#52 F. Вверх и вниз по дереву
#51 F. Самое короткое условие
#50 G. Истоки и стоки
#49 D. Охота за мышью
#49 F. Сессия в БГУ теорема Холла, алгоритм Куна (???) и так далее)
#48 F. Проекты дорог
#47 D. Взаимно простой граф
#46 E. Нужно больше боссов диаметр дерева мостов
#46 G. Два-пути ДП на дереве + дерево отрезков
#45 D. Граф и его дополнение
#45 F. Управление потоками
#45 G. Подсчёт GCD скрытый граф, функция Мёбиуса | центроидная декомпозиция
#44 G. Командные игроки скрытый граф, нахождение всех треугольников в заданном графе
#43 D. Degree Set (Множество степеней)
#43 F. Minimal k-covering (Минимальное k-покрытие) максимальный поток
#42 F. Рёбра на простых циклах фундаментальное множество циклов
#40 H. Подсчет путей ДП на дереве
Михаил Долинский

Темы: 1982
Сообщений: 47186

Мой профиль
#38 D. Покупка билетов алгоритм Дейкстра
#38 G. Кратчайшие пути метод динамической связности
#37 E. Связные компоненты?
#36 D. Почти ацикличный граф
#36 F. Несбалансированность дерева DSU
#35 F. Разрушение дерева
#34 G. Очередная задача про максимальный поток минимальный разрез + ДО
#33 C. Слух
#33 F. Минимум в поддереве двумерная структура данных: одно измерение соответствует глубинам вершин, а второе — времени входа в вершину в процессе DFS, sparse table
#32 G. Xor-MST алгоритмом Борувки
#29 F. Почти перестановка максимальный поток минимальной стоимости
#28 E. Берляндская химия скрытый граф
#27 G. Кратчайший путь? метод Гаусса
#25 E. Минимальные метки Topological labelling
#25 G. Запросы на дереве
#24 F. Создание уровней тернарный поиск
#24 G. Четыре мелодии скрытый граф, алгоритм Дейкстры с потенциалами Джонсона
#22 C. Догонялки
#22 F. Проверка на двудольность DSU, "разделяй и властвуй"
#21 F. Карточная игра скрытый граф, максимальный поток
#19 D. Сломанное BST сет
#18 D. Пути в полном бинарном дереве
#17 F. Вложение дерева bitmask DP on tree
#15 E. Анализ путей в функциональном графе бинарное возведение в степень | двоичный подъём
#14 D. Свопы в перестановке скрытый граф
#10 E. В погоне за артефактами мосты
#9 F. Волшебная матрица bitset | MST (минимальное покрывающее дерево графа) | двоичный подъём
#8 F. Медведь и справедливое множество теорема Холла, максимальный поток
#7 E. Муравьи в листьях
#6 E. Новогодняя ёлка дерево отрезков над Эйлеровым обходом
#4 E. Корень квадратный из перестановки скрытый граф, перестановки
#3 E. Минимальное остовное дерево по каждому ребру минимальное остовное дерево
#2 E. Lomsat gelral пересчет множеств на дереве
#2 F. Раскраска ребер двудольного графа
Михаил Долинский

Темы: 1982
Сообщений: 47186

Мой профиль
Теория чисел, игры, Другое - Горбатовский [Харрасов]

#151 F. Пловцы в бассейне функция Мёбиуса, БПФ
#150 F. Монокарп и стратегия - Сумма Минковского
#142 F2. Покраска графа (сложная версия) ДП, граф, комбинаторика, NTT (Number Theoretic Transform)
#142 E. Таблица и делители делители, факторизация, lower_bound, количество [простых] делителей
#139 D. Удачные цепочки НОД, простые делители, решето Эратосфена
#136 C. Карточная игра биномиальные коэффициенты одним из трех способов: треугольник Паскаля, предподсчет факториалов и обратных элементов, или предподсчет факториалов с использованием длинной арифметики.
#135 E. Красно-черный перец диофантово уравнение ax+by=n, расширенный алгоритм Евклида
#118 E. Сумасшедший робот теория игр, DFS/BFS
#117 D. X-магическая пара алгоритм GCD
#113 E. Восстановление турнирной таблицы meet-in-the-middle
#106 D. Количество пар НОД, НОК, решето Эратосфена
#102 G. Плитки NTT (Number-theoretic transform (integer DFT))
#99 C. Пинг-понг стратег.игра
#98 D. Радиовышки малая теорема Ферма, быстрое возведение в степень
#95 F. Одинаковое произведение НОД
#95 E. Ожидаемый урон вероятность, мат.ожидание, комбинаторика
#93 G. Соревнования по бегу - быстрое перемножение полиномов: алгоритм Карацубы или FFT
#92 E. Неоднозначность календаря сравнения, делители, сумма арифметической прогрессии
#92 A. Задача про LCM наименьшее общее кратное
#89 D. Два делителя решето Эратосфена, факторизация
#86 C. Очередная задача на подсчет свойства остатков по модулю
#83 F. Атака на Красное Королевство теория Шпрага-Гранди
#82 D. Заполни сумку анализ битов в двоичном представлении
#81 D. Одинаковые GCD функция Эйлера, факторизация
#80 D. Задача Минимакс битовое представление массивов
#79 D. Робот Деда Мороза
#77 C. Бесконечный забор gcd
#76 G. Множество делителей диаграмма Хассе, найти последовательность в OEIS, ДП-рюкзак, умножение многочленов с помощью FFT, D-n-C (разделяй и властвуй)
#76 F. Сделай их похожими 2 раза по 15 битов, meet-in-the-middle
#75 F. Красно-белый забор FFT - NTT перемножение полиномов
#74 A. Вычитание простого простые делители
#66 F. Количество подперестановок XOR
#65 B. Lost Numbers интерактивная задача
#63 E. Угадай корень интерполяция многочлена
#63 C. Будильники повсюду делители, НОД

#60 D. Магические камни возведение матрицы в степень
#59 D. Сжатие GCD
#58 B. Цифровой корень S(x)=(x-1) mod 9 +1
#58 G. Ошибка сервера перевода
#57 G. Счастливые билеты двоичное возведение в степень с перемножением многочленов с помощью NTT
#51 C. Вася и мультимножества 2 мультисета
#50 E. Покрытые точки Отрезок покрывает ровно GCD(|x1-x2|,|y1-y2|)+1 точек с целыми координатами.
#50 F. Взаимно простые степени Формула Мёбиуса
Михаил Долинский

Темы: 1982
Сообщений: 47186

Мой профиль
#49 G. X-мышь в общежитии
#48 G. Подходящая команда
#41 G. Разбиения числа Стирлинга второго рода
#37 D. Емкости задача о переливаниях
#37 G. Список чисел Факторизация, формула включений-исключений, бинпоиск
#36 G. Простые массивы функция Мёбиуса, формула включений-исключений
#35 D. Подсчет инверсий перестановки
#33 E. Подсчет массивов факторизация, бинарное возведение в степень
#32 D. Почти тождественные перестановки
#32 E. Максимальная подпоследовательность meet-in-the-middle
#31 C. Метро Бергорода перестановки
#26 E. Васина функция факторизация, НОД
#24 E. И снова карточная игра факторизация, метод двух указателей
#20 F. Взаимно простые подпоследовательности функция Мёбиуса, формула включений-исключений
#14 E. Xor-последовательности бинарное возведение в степень матрицы
#14 F. Couple Cover решето Эратосфена
#13 D. Итерированная линейная функция бинарное возведение в степень матрицы
#12 D. Красивое подмножество решето Эратосфена
#11 F. Медведь и боулинг 4 разделяй и властвуй
#9 E. Вор в магазине быстрое преобразование Фурье



Опрос
- считаете ли Вы такие занятия полезными, чтобы продолжать?
- успел ли придумать решение хоть одной задачи? Какой(Каких) – указать тему(ы)
- чему научились на этом занятии?
- чья задача/рассказ оказался для Вас наиболее полезным?
- чья задача/рассказ оказался для Вас наиболее понятным?
- будете ли Вы дорешивать какие-то из этих задач? Какие, Почему?
- как предлагаете изменить форму проведения занятий?
например
-- нужны ли предзаказы:
... Вы просматриваете задачи и просите конкретную задачу у рассказчика
... а он по возможности в первую очередь рассматривает заказанные задачи
-- нужно ли обязательное дорешивание
-- может не ограничиваться только задачами Educational Rounds

А мы что-то из этого не знаем?
А надо?


Кружки Tinkoff-generation

3 курс

Преподаватели:

Филипп Грибов (grphil)
Даниил Николенко (qoo2p5)

Программа группы рассчитана на школьников уровня дипломантов и участников Всероссийской олимпиады, имеющих представление об алгоритмах уровня параллелей A'-A ЛКШ. В первом полугодии изучались такие темы как convex hull trick, divide and conquer, центроидная декомпозиция, small-to-large, heavy-light декомпозиция, лестничная декомпозиция, алгоритм Фараха-Колтона и Бендера, теория Гранди, альфа-бета отсечение, быстрое преобразование Фурье, персистентные структуры данных, двумерные деревья отрезков, корневые декомпозиции, суффиксный автомат, алгоритм Куна и его применения, эйлеровы графы, а также некоторые другие алгоритмы и структуры данных.

В начале занятия мы проводим разбор предыдущих контестов. Оставшееся время занято лекцией или семинаром (школьники придумывают решения задач с листочка, рассказывают их преподавателям, во время занятия проводится разбор этих задач).

На неделю даем два тура. Один тематический, который можно решать всю неделю, а после разбора дорешивать, и один дистанционный — виртуальный пятичасовой тур в формате Всероссийской олимпиады.


2 курс

Преподаватели:

Максим Деб Натх (DebNatkh)
Сергей Слотин (sslotin)
Артем Рябов (SoMuchDrama)
Андрей Чулков (achulkov2)

Второй курс рассчитан на уровень участников и призеров региона, потенциальных участников и призеров всеросса, знакомых с простыми алгоритмами уровня параллелей С-B’ ЛКШ. Занятия длятся 5 часов и проводятся в группах до 15 человек. На занятиях дается необходимый теоретический материал, а также разбираются задачи на пройденную тему. Список тем, изученных в первом полугодии: дерево отрезков, декартово дерево, Z- и префикс- функции, бор, Ахо-Корасик, полиномиальное хеширование, LCA и связанные задачи, минимальный остов, динамическое программирование на примерах задач различной сложности.

1 курс

Преподаватели:

Андрей Гаркавый (andrewgark)
Максим Гришкин (riskingh)
Глеб Лобанов (Glebodin)
Антон Алешин

Программа курса рассчитана на начинающих школьников уровня призеров муниципального этапа, умеющих решать простые задачи по информатике в тестирующей системе на языке C++ или Питон. В первом полугодии уже изучались такие темы как сортировки, теория чисел, жадный алгоритм, STL, динамическое программирование (включая рюкзак и НВП-НОП), сканирующая прямая, графы, DFS и BFS.

Занятия состоят из лекции по теме и тематического контеста, обычно на informatics.mccme.ru. Часто дается еще один практический контест с олимпиадными задачами. Эти контесты далее можно и нужно дорешивать дома.
Михаил Долинский

Темы: 1982
Сообщений: 47186

Мой профиль

Результаты решения олимпиад IOI  

                  2017              2016              2015               2014              2018
Костяной    бронза(152>137)  бронза(264>240)    бронза(254>185)    бронза(297>223)    бронза(253>187) 
Харрасов            43              172                141                153                132
Ермаков             40               80                154                179                195

Результаты дорешивания олимпиад IOI 

                2017                  2016             2015               2014             2018
Костяной    серебро(327>249)   серебро(354>328)   серебро(409>325)   золото(476>449)  золото(336>334)
Харрасов             33         бронза(263>240)    бронза(227>185)         -                -  
Ермаков               -         бронза(263)        бронза(275)       бронза(259)            - 

Для справки
http://stats.ioinformatics.org/results/2018     (2017, 2016 …)

      Золото  Серебро  Бронза
2018   334      272      187 
2017   353      249      137 
2016   416      328      240    
2015   440      325      185
2014   449      323      223
2013   480      359      220

Checklist for OI Problems (WebApp)


Надо обсудить стратегию/технологию решения задач на олимпиаде.

Предлагаю «для затравки» такую

1 час
– чтение условий
- придумывание решений на «бронзу» (одну или несколько первых групп в каждой задаче)
- фиксация «проблем», требующих решения на серебро/золото в каждой задаче

1.5 часа
- нарешивание на бронзу
- “на подкорке” обдумывание зафиксированных проблем

1 час
- попытка решения всех зафиксированных проблем
- выбор одной-двух-трёх задач, которую будешь добивать до «серебра-золота»
- придумывание выбранного на «серебро-золото»

1.5 часа
- дорешивание на серебро-золото


Грубо говоря

Бронза    - 35% баллов 
Серебро   - 60% 
Золото    - 80%



Если у тебя есть своя стратегия-технология или ты хочешь подкорректировать мою,
сделай до олимпиады – напиши мне и постарайся придерживаться её хоть одну олимпиаду.

Потом если нужно снова корректируешь, пишешь мне и снова стараешься придерживаться.
И так пока не выработаешь «стратегию» (технологию), ГАРАНТИРУЮЩУЮ максимальный результат при любых задачах и любом твоём самочувствии.
Михаил Долинский

Темы: 1982
Сообщений: 47186

Мой профиль
Сводные результаты без фамилий
 6. 644 Мищенко 
10. 593 Ермаков
11. 590 Харрасов
...
52. 450 Козлов
-------------

Без дипломов
57. 433 Бирич
78. 401 Ситников

Давайте улучшать позиции !!!

Начать с
1. Дорешивание областной олимпиады на максимально возможное для себя количество баллов
2. Решить библиотечные задачи республик прошлых лет
Как минимум:
17_BY. Находка (70 баллов)
11_BY. Горячо-холодно
18_BY. Поиск в перестановке (60 баллов)
12_BY. Дробь (45 баллов)
16_BY. Палитра
14_BY. Сейф
 
Индекс форума ->Олимпиадное программирование ->Методика подготовки к IOI 2007 - ... 1, 2, 3, 4
Time:0,078