Сборная РТУ МИРЭА по спортивному программированию

  • В РТУ МИРЭА в рамках сообщества активных студентов, которым интересно решать сложные алгоритмические задачи, осуществляется подготовка в рамках спортивного программирования. Сформирована сборная РТУ МИРЭА, состоящая из  нескольких команд, но принять участие в подготовке может каждый студент.

    Тренеры сборной, имеющие богатый олимпиадный опыт, регулярно проводят занятия по спортивному программированию как для начинающих олимпиадников, так и для более опытных и сильных алгоритмистов. На занятиях разбираются методы решения олимпиадных задач, читаются специализированные лекции по алгоритмам и специальным разделам математики. С основным составом сборной обсуждаются глубокие детали стандартной библиотеки C++ (STL) для компилятора GCC и оптимизации кода.

    Ежемесячно проходят тренировочные соревнования для всех желающих  с последующим разбором задач. На этих соревнованиях студентам предлагается за четыре часа решить шесть задач. После этого результаты фиксируются, и участникам даётся неделя, чтобы в свободное время закончить решение задач. Затем публикуется разбор заданий, и обсуждаются решения.

    Наиболее активным участникам программы университет оплачивает участие в различных сборах по спортивному программированию, на которых ребята слушают лекции по теории алгоритмов и решают задачи.

    Занятия проходят в аудитории Д108.

    С 2020 года начата на базе детского технопарка РТУ МИРЭА "Альтаир" начата подготовка школьников по спортивному программированию.

    Занятия проводят тренеры сборной РТУ МИРЭА по спортивному программированию. В рамках подготовки ребята проходят различные алгоритмы и их приложения, разбирают технические аспекты языков и особенности языков программирования. Регулярно проводятся интенсивы по решению задач с последующим разбором и обсуждением решений. Ежемесячно проводятся тренировочные соревнования, приближенные по формату к реальным олимпиадам. Занятия проходят раз в неделю длитейльностью 3 часа. Ежемесячно проводятся тренировочные соревнования.

  • Строганов Андрей Валентинович
    Руководитель программы
    Доцент кафедры высшей математики Института кибернетики
    Телефон: +7 499 215-65-65 (доб. 4001)
    E-mail: stroganov@mirea.ru
    Telegram: @savthe
    Козырев Дмитрий Сергеевич
    Главный тренер
    Призер командных и личных олимпиад по математике, призер RuCode Autumn 2020
    E-mail: dmkozyrev@rambler.ru
    Telegram: @dmkozyrev
    Кичак Евгений Петрович
    Тренер
    Многократный победитель и призер международных и всероссийских олимпиад по математике, призер RuCode Autumn 2020
    Игнатьев Анатолий Сергеевич
    Тренер
    Призер RuCode Autumn 2020, победитель RuCode 2.5, призер ICPC NERC 2020, призер ICPC Moscow Regional Contest 2020
    Волков Денис Александрович
    Тренер
    Опытный С++ и Python разработчик
  • Тематика занятий со старшей командой сборной:
    1. Продвинутая комбинаторика. Метод включений-исключений
    2. Полный перебор. Метод встречи посередине
    3. Бинарный и тернарный поиск в интерактивных задачах
    4. Применение поиска в ширину в задачах динамического программирования
    5. Алгоритмы 0-1-bfs и multi-source bfs
    6. Использование Дерева Отрезков в задачах комбинаторики и динамического программирования
    7. Метод сканирующей прямой. Обработка событий offline
    8. Бинарный поиск по ответу
    9. Совместное использование бинарного поиска и Sparse Table
    10. Динамическое программирование на подмножествах
    11. Метод двух указателей. Алгоритм Мо и корневая декомпозиция
    12. Центроид и диаметр дерева
    13. Система непересекающихся множеств
    14. Решето эратосфена, простые делители, перебор всех делителей по разложению на простые
    15. Матрицы, СЛАУ и алгоритм Гаусса в олимпиадных задачах
    16. Префиксное дерево

    На занятиях с младшей командой сборной изучаются:
    1. Техника программирования
    2. Основные целочисленные алгоритмы
    3. Комбинаторные задачи
    4. Бинарный поиск
    5. Жадные алгоритмы
    6. Задачи на строках
    7. Работа со стандартными контейнерами
    8. Элементы динамического программирования

    На занятиях со школьниками изучаются:
    Необходимо понимать, что:
    • данный план не является точно разделенным по занятиям. Некоторые темы могут проходиться за половину занятия, некоторые могут изучаться в течение 3-4-х занятий суммарно.
    • в данном плане приведены лишь приблизительный набор тем, которые планируется изучать. Важной частью подготовки к олимпиадам является решение задач различного спектра (не обязательно тематических), которое должно идти параллельно с изучением специальных тем.

    План занятий:
    1. Введение. Историческая  справка. Обзор курса. Пример задач. 
    2. Языки программирования. Императивные языки программирования. Общие черты и различия. Основные типы данных и базовые операции.
    3. Условный оператор. Булева алгебра. Основные логические операции.
    4. Операторы цикла. 
    5. Системы счисления. Двоичная система счисления. Представление целых чисел в памяти компьютера. Переполнение. Побитовые операции, отличие от логических. Дополнительный код. 
    6. Вещественные числа. Представление вещественных чисел в компьютере. Понятие машинного эпсилон. Специальные значения: бесконечность, NaN. Стандартные математические операции.
    7. Понятие массива. Индексация. Многомерный массив. 
    8. Понятие и свойства алгоритма. Сложность алгоритма и ее оценка. Нотация сложности и ее свойства. Лучший, средний и худший случаи сложности. Оценка потребляемой памяти.
    9. Структуры данных. Массив как фундаментальная структура данных. Вставка и удаление из массива. Поиск: линейный. Поиск минимума/максимума в массиве.
    10. Символы, ASCII-код и Unicode. Строки. Ссылочные типы данных. Доступ к символам строки. Основные операции над строками и их сложность. Иммутабельные типы данных. Конкатенация строк.
    11. Запросы на отрезке без обновлений. Префиксные и суффиксные суммы. Обобщение на другие операции: минимум/максимум на префиксе/суффиксе; обратимые операции на отрезке.
    12. Функции и методы. Параметры и переменные. Сигнатура и перегрузка методов. Рекурсия. Переполнение стека рекурсии. Рекурсивные определения, структуры и алгоритмы. Хвостовая рекурсия. Мемоизация и рекурсия с сохранением. Оценка сложности рекурсивного алгоритма.
    13. Сортировка массива. Квадратичные алгоритмы сортировки: пузырьком, вставками, выборкой. Принцип «разделяй и властвуй». Линейно-логарифмические алгоритмы сортировки: слиянием. Оценка оптимальной сложности алгоритмов сортировки.
    14. Принцип «разделяй и властвуй». Линейно-логарифмические сортировки: быстрая. Количество инверсий в массиве за O(NlogN). Поиск K-ой порядковой статистики за O(N).
    15. Понятие монотонности. Поиск: двоичный – вещественный и целочисленный. Регулярный двоичный поиск. Понятие унимодальности. Поиск: троичный – вещественный. 
    16. Теория чисел. Модулярная арифметика. Сложение, вычитание, умножение по модулю. Быстрое возведение в степень.
    17. Теория чисел. Делители числа. Поиск делителей числа. НОД, НОК. Алгоритм Евклида. Простые числа. Решето Эратосфена. Факторизация числа. Вычисление количества делителей числа по факторизации.
    18. Динамическое программирование: определение, базовые типы задач.
    19. Структуры данных: стек, очередь, двунаправленная очередь.
    20. Структуры данных: очередь с приоритетами – куча. Сложность операций кучи. Линейно-логарифмические сортировки: сортировка кучей. Модификация кучи для быстрого удаления. 
    21. Объектно-ориентированное программирование. Понятие объекта. Классы: поля, методы. Понятие ссылки на себя (this/self). Конструкторы. Модификаторы доступа.
    22. Объектно-ориентированное программирование. Наследование. Переопределение методов. Абстрактные и виртуальные классы и методы.
    23. Понятие множества. Свойства множеств. Понятие ассоциативного массива. Свойства ассоциативных массивов. Понятие хеш-функции. Хеш-таблица. Построение множества и ассоциативного массива на основе хеш-таблицы. Оценка сложности операций структур на основе хеш-таблицы.
    24. Понятие дерева. Дерево поиска. Двоичное дерево поиска. Сбалансированные и самобалансирующиеся двоичные деревья поиска (обзор): AVL, красно-черное, декартово. Построение множества и ассоциативного массива на основе двоичного дерева поиска. Оценка сложности операций структур на основе двоичного дерева поиска. 
    25. Понятие графа. Вершины графа, их атрибуты. Ребра графа, их атрибуты. Хранение графа: матрица смежности, списки смежности, список ребер. Обходы графа: в глубину, в ширину. Компоненты связности.
    26. Поиск кратчайшего пути в невзвешенном графе. Поиск цикла в графе. Топологическая сортировка. Компоненты сильной связности. Эйлеров цикл и путь.
    27. Деревья. Понятия предка и потомков. Особенности деревьев по сравнению с графами общего вида. Вычисления на спуске и подъеме. Принцип слияния меньшего к большему. Динамическое программирование на поддеревьях. Код Прюфера.
    28. Алгоритмы поиска кратчайших путей во взвешенном графе: Дейкстры, Форда-беллмана, Флойда. 
    29. Система непересекающихся множеств (СНМ). Основные операции. Модификации: сжатие путей, ранговая эвристика, персистентность.
    30. Остовные деревья графа. Построение остовного дерева: поиск в глубину, поиск в ширину. Разложение на базис циклов. Минимальное остовное дерево во взвешенном графе. Алгоритмы поиска минимального остова: Прима, Крускала.
    31. Запросы на отрезке без обновления: разреженная таблица. НОД/максимум/минимум на отрезке.
    32. Запросы на отрезке с обновлением: sqrt-декомпозиция. Список на sqrt-блоках. Sqrt-декомпозиция запросов. Алгоритм МО.
    33. Запросы на отрезке с обновлением: дерево Фенвика. Изменение элемента, запрос суммы. Прибавление на отрезке, запрос элемента. Поиск префикса максимальной ограниченной суммы.
    34. Запросы на отрезке с обновлением: дерево отрезков. Изменение одиночного элемента, запрос на отрезке.
    35. Запросы на отрезке с обновлением: дерево отрезков. Теорема о разбиении на log-отрезков. Ленивые операции. Изменение на отрезке.
    36. Запросы на отрезке с обновлением: дерево отрезков. Сохранение всех элементов на отрезке. Частичное каскадирование. Двумерное дерево отрезков.
    37. Наибольший общий предок (LCA). Алгоритм двоичного подъёма. 
    38. Запросы на поддеревьях. Эйлеров обход дерева. Сведение LCA к RMQ. 
    39. Перебор всех перестановок за O(N!). Вычисление лексикографического номера по перестановке. Генерация перестановки по номеру.
    40. Битовые операции. Работа с целыми числами как с битовыми масками. Перебор всех подмножеств за O(2^N). Динамическое программирование на подмножествах.
    41. Геометрия на плоскости. Векторная арифметика. Скалярное и векторное произведения. Виды уравнения прямой. Расстояние от точки до прямой. Пересечение прямых. Пересечение отрезков.
    42. Геометрия на плоскости. Выпуклые многоугольники. Ориентированная площадь многоугольника.
    43. Геометрия на плоскости. Окружность. Пересечение окружностей. Пересечение прямой и окружности.
    44. Строковые алгоритмы: Хеш-функция. Полиномиальный хеш строк. Алгоритм Рабина-Миллера. Поиск количества различных подстрок за O(N^2). Поиск всех палиндромов за O(NlogN). Хеш-функция для двумерного случая.
    45. Строковые алгоритмы: Z и префикс-функции. Алгоритм Кнута-Морриса-Пратта. Префиксный автомат. Поиск количества различных подстрок за O(N^2). Алгоритм Манакера.
    46. Строковые алгоритмы: Бор. Алгоритм Ахо-Корасик. Сжатый бор.
    47. Строковые алгоритмы: Суффиксный массив. Построение за O(Nlog^2N) и O(NlogN).  Сравнение подстрок за O(1). Поиск LCP подстрок за O(1).
  • Как стать участником программы РТУ МИРЭА по спортивному программированию

    Группа студентов 

    Заходите в группу: https://vk.com/mireacoding, приходите на любое занятие, и тренер включит вас в Телеграм-канал, где обсуждаются задачи, публикуются новости о предстоящих событиях, планируются составы команд для внешних соревнований.

    От претендентов на участие в сборной ждут наличия определённых знаний, т.к. начального курса программирования нет. Ожидается, что студенты уже свободно владеют инструкциями циклов, массивами, умеют находить максимум в массиве, НОД двух чисел и т.д.

    Группа школьников

    Группа школьников для занятий по спортивному программированию отбирается по результатам собеседования. Ежегодно отбираются две группы по 13-15 человек. Отбор проводится в форме олимпиады по программированию, где ребятам предлагается 6-8 задач на 4 часа. По итогам олимпиады школьников рекомендуют к зачислению в группы.

  • Занятия по спортивному программированию со школьниками

    В рамках клуба проводятся занятия со школьниками по спортивному программированию. Тренеры сборной РТУ МИРЭА по спортивному программированию готовят школьников к успешному выступлению на олимпиадах муниципального и регионального уровней. 

    Целевая аудитория – школьники 9-10-х классов, владеющие базовыми навыками программирования.

    Ценность данного курса. Безусловно, владение навыками программирования на сегодняшний день является значительным конкурентным преимуществом на рынке труда. Тем не менее, в случае конкуренции в среде программистов, владение основными навыками программирования, которое обычно развивается сначала в школе, а затем и в университете, не является отличительной чертой. Существенными факторами становятся знания в области конкретных технологий (фреймворков, наборов инструментов, заточенных под выполнение определенных задач) и углубленные знания алгоритмов, структур данных и умение их применять в прикладных задачах. И если конкретные технологии и фреймворки меняются каждый год, то алгоритмы и структуры данных, лежащие в основе разработки эффективных программ, остаются неизменными. Именно поэтому изучение данных подходов и закрепление соответствующих навыков при помощи решения олимпиадных задач является лучшей инвестицией среди прочих на пути становления ценным специалистом в сфере разработки программного обеспечения.

    Для тех ребят, которые в будущем планируют продолжить учебу в РТУ МИРЭА, данный курс позволит получить необходимые навыки для участия в студенческой сборной РТУ МИРЭА по спортивному программированию.

    Рекомендуемые начальные знания. Стандартный школьный курс программирования:
    1. Типы данных, переменные, константы
    2. Инструкции ветвления
    3. Инструкции циклов
    4. Массивы, в том числе многомерные

    Задачи будут разбираться преимущественно на C++, иногда на Python.

  • Наши достижения

    2020 год

    13.12.20 команды сборной МИРЭА стали призерами ICPC NERC 2020 и получили дипломы третьей степени (Third Award)

    06.12.20 Команды сборной МИРЭА стали победителями и призерами международного чемпионата по алгоритмическому программированию RuCode 2.5

    15.11.2020 Команды сборной РТУ МИРЭА впервые за последние 16 лет вышли в полуфинал Международного студенческого чемпионата мира по программированию ICPC. В отборочном этапе Moscow Regional Contest приняли участие шесть команд от нашего ВУЗа. 

    4.10.2020 Команды сборной РТУ МИРЭА стали призерами и победителями чемпионата по алгоритмическому программированию в рамках осеннего международного фестиваля RuCode 2020

    5-12 сентября, 2020. Команды РТУ МИРЭА заняли 3 и 9 места на сборах по алгоритмическому программированию и ИИ Discover World 2020.