[Logo] Форум DL
  [DL]  Back to home page 
Forum Index ->Олимпиадное программирование ->Методика подготовки к IOI 2007 - ...
Author Message
Mihail Dolinskiy

Topics: 1530
Messages: 36538

My Profile
Общие идеи (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:


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

Topics: 1530
Messages: 36538

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

#539 Div.1 E. Саша и очень лёгкий тест дерево отрезков, факторизация
#560 Div.3 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. Лягушки и комары динамическое дерево отрезков
Mihail Dolinskiy

Topics: 1530
Messages: 36538

My Profile
Строковые структуры и ДП - Костяной

#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. Суффиксы Фибоначчи
#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. Сделай палиндром
Mihail Dolinskiy

Topics: 1530
Messages: 36538

My Profile
ДП - Харрасов [Ермаков, Бирич]

#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. Соедини вершины
#27 F. Охранники на складе ДП по изломанному профилю
#26 D. Круглое подмножество
#22 D. Две мелодии
#20 E. Рома и покер
#19 F. Мышки и норки ДП + deque с минимумами (или очередь на двух стеках)
#15 F. Футболки (решение обсуждается в комментариях)
#13 E. Очередной турнир ситхов ДП по битмаскам
#12 F. Четыре делителя ДП + решето Эратосфена + дерево Фенвика
#8 D. Волшебные числа ДП по числу
#4 F. Робот на кольце
Mihail Dolinskiy

Topics: 1530
Messages: 36538

My Profile
Графы-Костяной

#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. Подсчет путей ДП на дереве
#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 алгоритмом Борувки
Mihail Dolinskiy

Topics: 1530
Messages: 36538

My Profile
#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. Раскраска ребер двудольного графа
Mihail Dolinskiy

Topics: 1530
Messages: 36538

My Profile
Теория чисел, Другое - Горбатовский [Харрасов]

#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. Взаимно простые степени Формула Мёбиуса
#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. Вор в магазине быстрое преобразование Фурье
Mihail Dolinskiy

Topics: 1530
Messages: 36538

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

Topics: 1530
Messages: 36538

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


Кружки 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. Часто дается еще один практический контест с олимпиадными задачами. Эти контесты далее можно и нужно дорешивать дома.
Mihail Dolinskiy

Topics: 1530
Messages: 36538

My Profile

Результаты решения олимпиад 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%



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

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

Topics: 1530
Messages: 36538

My Profile
Сводные результаты без фамилий
 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. Сейф
Mihail Dolinskiy

Topics: 1530
Messages: 36538

My Profile
Удобный и мощный 3-строчник для дебага (C++17 эдишн)

С++ 17 на DL тоже поддерживается в g73

Отладка в C++

И здесь
много всякой всячины по С++ с Codeforces

Просмотрите – может найдёте что-то полезное
Mihail Dolinskiy

Topics: 1530
Messages: 36538

My Profile
Дорешивание с июня 2018

IOI 2018
Костяной - 3
Харрасов - 2
Mihail Dolinskiy

Topics: 1530
Messages: 36538

My Profile
#68 G. Очередная мемная задача цифровая динамика (ДП по числу) на 7-мерном массиве - или состояния обозначаются специальными структурами, и эти структуры хранятся в map

Если вы полностью уверены в своих навыках программирования, вы можете просто написать эту динамику на 7-мерном массиве. Я очень не хотел начинать это писать (однако смотря на решения участников, я вижу, что это звучит куда страшнее, чем выглядит в коде), поэтому в авторском решении по этой задаче все состояния обозначаются специальными структурами, и эти структуры хранятся в map. Это довольно известная техника: когда то решение динамическим программированием, которое вы придумали, включает в себя очень сложные состояния и переходы, иногда лучше для состояний динамики написать свою структуру, и хранить структуры в хэш-таблице или map. У этой техники есть несколько плюсов:

иногда ее гораздо проще писать (код может получиться длиннее, чем у такого же решения на многомерном массиве вместо структур, но писать и понимать его сильно проще);
если много состояний являются недостижимыми, то мы их вообще никак не будем рассматривать;
иногда можно очень легко добавлять различные оптимизации, связанные с общим числом различных состояний динамики. Например, количество различных значений mask1 и mask2 может быть очень большим, но его можно уменьшить следующим образом: как только мы найдем пару цифр в mask1 и mask2, которые подходят для x? и y?, можно заменить эти маски на какие-то значения, которые будут обозначать, что это состояние уже «закончено» (мы нашли нужную нам пару цифр), и никогда больше эти маски не менять.
 
Forum Index ->Олимпиадное программирование ->Методика подготовки к IOI 2007 - ...
Time:0,11