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

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

    Тренеры сборной, имеющие богатый олимпиадный опыт, регулярно проводят занятия по спортивному программированию как для начинающих олимпиадников, так и для более опытных и сильных алгоритмистов. На занятиях разбираются методы решения олимпиадных задач, читаются специализированные лекции по алгоритмам и специальным разделам математики. С основным составом сборной обсуждаются глубокие детали стандартной библиотеки 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.

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

    25.04.2021. RuCode 3.0

    Три команды сборной РТУ МИРЭА стали призерами финального чемпионата по алгоритмическому программированию RuCode 3.0 дивизиона C/D:

    SortirovkaWalrusom (Смирнов Андрей, Матчин Артемий и Гаврильев Валерий) - решили 5 задач

    MIREA AniMates (Игнатьев Анатолий, Идрисов Ибрагим и Петров Кирилл) - решили 4 задачи

    XYZI Team (Хохлов Кирилл, Громов Валентин и Проценко Иван) - решили 4 задачи.

    От диплома победителей ребят отделили 1-2 задачи.

    Итоговая таблица доступна по ссылке http://opentrains.mipt.ru/~ejudge/secretABzzz

    Несмотря на приложенные усилия и волю к победе, командам "Merge IT" (Гребнев Никита, Черепанов Артем и Марченко Вадим) и "Bonuses&Conuses" (Скаев Сармат, Лазин Максим и Баринов Вячеслав) немного не хватило до призовой зоны.

    13.12.2020. ICPC NERC 2020

    Две команды сборной РТУ МИРЭА стали призерами полуфинала чемпионата мира по программированию ICPC Northern Eurasia Regional Contest 2020:

    This name already exists (Волков Виктор, Автушко Даниил и Игнатьев Анатолий) - 5 задач.

    AniMates (Шамсутдинов Булат, Петров Кирилл и Идрисов Ибрагим) - 5 задач.

    Впервые за 16 лет команды РТУ МИРЭА прошли в полуфинал самого престижного соревнования в Северной Евразии, но они не только прошли, а еще и выиграли дипломы третьей степени (Third Award)! Все члены команд, а также их тренеры Козырев Дмитрий и Кичак Евгений, были награждены дипломами третьей степени!

    06.12.2020. RuCode 2.5

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

    This name already exists (Гаврильев Валерий, Волков Виктор и Игнатьев Анатолий) финишировала с 9-ю правильно решенными задачами и стала победителем дивизиона C/D.

    AniMates (Шамсутдинов Булат, Петров Кирилл и Идрисов Ибрагим) заняли призовое место с 8 решенными задачами.

    XYZI Team (Иван Проценко, Алексей Антипин и Кирилл Хохлов) стали призёрами, решив 6 задач.

    Ещё несколько команд сборной РТУ МИРЭА участвовали в чемпионате, но, к сожалению, не попали в призовую зону. Среди них команды "memrea team" (Платов Игорь, Мезенов Даниил и Жарков Богдан), "Fresh_meat" (Скаев Сармат, Лазин Максим и Баринов Вячеслав) и "Merge IT" (Черепанов Артем, Гребнев Никита и Марченко Вадим). Ребятам из этих команд удалось правильно решить от 2 до 3 задач.

    Итоговая турнирная таблица доступна по ссылке http://rucode.it-edu.mipt.ru/lited10resCD

    15.11.2020. ICPC Moscow Regional Contest

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

    Команда "This name already exists" (Волков Виктор, Автушко Даниил и Игнатьев Анатолий) решила 7 задач и проложила себе путь в полуфинал чемпионата. По результатам четвертьфинала члены команды вместе с тренером Евгением Кичаком были награждены дипломом третьей степени.

    Команда "AniMates" (Шамсутдинов Булат, Петров Кирилл и Идрисов Ибрагим) успешно справилась с шестью задачами. Высокая скорость выполнения заданий и безошибочность их решения - вот ключ, открывший ребятам дверь в полуфинал чемпионата. Персональным тренером команды является Козырев Дмитрий.

    Команде "Sortirovka Walrusom" (Гаврильев Валерий, Смирнов Андрей и Матчин Артемий), решившей также 6 задач, к сожалению, в полуфинал выйти не удалось из-за большого штрафного времени.

    Еще 3 команды выступали впервые, это: "XYZI Team" (Иван Проценко, Алексей Антипин и Кирилл Хохлов) - решили 4 задачи, "MEMREA" (Тимур Ибрагимов, Даниил Мезенов и Богдан Жарков) - 2 задачи, "Bonuses&Conuses" (Вячеслав Баринов, Сармат Скаев и Максим Лазин) - 2 задачи. Это является очень хорошим результатом для первого раза.

    4.10.2020. RuCode 2

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

    В чемпионате нем приняли участие 819 команд (включая зарубежные команды) и более 2000 человек. От нашего вуза выступали 7 команд, 5 из которых стали призерами, и одна команда - победителями!

    Команды-призеры в старшей номинации (дивизион C)

    AniMate (Шамсутдинов Булат, Петров Кирилл и Идрисов Ибрагим).

    MIREA Pocket Rocket Club (Кичак Евгений, Кондратов Юрий и Козырев Дмитрий).

    Sortirovka Walrusom" (Гаврильев Валерий, Смирнов Андрей и Матчин Артемий).

    This name is already exists (Волков Виктор, Автушко Даниил и Игнатьев Анатолий).

    Победители и призеры в младшей номинации (дивизион D)

    memrea team (Мезенов Даниил, Платов Игорь и Жарков Богдан) - победители.

    Not merge team (Черепанов Артём, Гребнев Никита, Макшаков Николай) - призеры.

    Команда "CHASER" (Алиев Мишан, Мстоян Амиран, Савенков Константин), к сожалению, не вошла в призовую зону.

    26.04.2020 RuCode

    Команда сборной РТУ МИРЭА SortirovkaWalrusom (Гаврильев Валерий, Смирнов Андрей, Матчин Артемий) завоевала малую бронзовую медаль на Всероссийском учебном фестивале по искусственному интеллекту и программированию.

    5-12 сентября, 2020. Discover World 2020

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

    Студенты Института Информационных технологий Валерий Гаврильев и Артемий Матчин заняли третье место в итоговом командном контесте Discover World 2020, Division C: Final Team Contest. Ребята решили столько же задач, сколько и победители, но набрали больше штрафного времени по ходу соревнования.

    Студенты Института Кибернетики Анатолий Игнатьев и Ибрагим Идрисов заняли 9-е место, решив на одну задачу меньше, чем победители.