Спортивное программирование

🔨 Вот уже четвёртые сутки жюри RuCode 2026 продолжает банить читеров, которые использовали нейросети при решении задач. У них появляется надпись LLM. Сергей Кирьяков из группы КМБО-01-22 (Институт Искусственного Интеллекта) уже в топ-3, остальные студенты РТУ МИРЭА тоже поднимаются вверх по турнирной таблице. Следите за результатами?

Ребята, желающие присоединиться к июльскому интенсиву и указавшие для связи ВК, откройте личные сообщения. Или оставьте в форме актуальный тг 👁

6 июля начинается летний интенсив «Быстрый старт в спортивном программировании» от Института Искусственного Интеллекта 🩵 За четыре недели ты разберёшь шесть ключевых тем спортивного программирования, погрузишься в регулярные тренировки и проверишь свои силы на итоговом чемпионате. Обучение будет выстроено в таком формате: лекция по новой теме 💙три дня на решение контеста 💙подробный разбор задач 💙переход к следующей теме. Предусмотрена внутренняя система оценки, в рамках которой за тренировочные контесты можно набрать до 600 баллов, и ещё до 400 баллов — на финальном чемпионате. 🦋 Для студентов Института Искусственного Интеллекта есть дополнительный бонус: результаты обучения могут быть учтены в осеннем семестре по профильным дисциплинам. Давно хотел попробовать себя в спортивном программировании? Скорее заполняй форму и присоединяйся к нам 6 июля. За ответами на оставшиеся вопросы обращайся к @i_hate_foobar.

🕵️‍♂️ В новом видео решаем задачи тренировочного контеста международного чемпионата по алгоритмическому программированию РуКод 2026 и анализируем, что же приготовили авторы для определения нашего уровня подготовки к онлайн-чемпионату.

Встречаемся через 10 дней на долгожданном онлайн-чемпионате РуКод 2026 🥹 Он состоится 28 июня с 11:00 по 14:00 МСК. Формат участия — индивидуальный, а соревноваться можно даже из дома. Чемпионат пройдёт в трёх дивизионах: A-B, C-D и E-F. Все участники получат сертификаты, а лучшие — дипломы победителей и призёров. Чтобы участвовать, необходимо пройти регистрацию на сайте МФТИ: ➡️ авторизуйся, если уже зарегистрирован, восстанови пароль, если забыл, либо зарегистрируйся заново; ➡️ заполни анкету, обязательно выбрав подходящий дивизион и ответив «да» в вопросе об участии в чемпионате 28 июня; ➡️ пройди тренировочный контест, ознакомься с материалами и сохрани логин и пароль. Если ты — студент РТУ МИРЭА, обязательно заполни форму, а возникшие вопросы задавай @i_hate_foobar.

👨‍💻 Сегодня разберём задачу «Максимальный НОД». В ней нужно построить строго возрастающую последовательность a[1], a[2], ..., a[k] из k натуральных чисел так, чтобы их сумма была равна n, а наибольший общий делитель был максимален среди всех возможных вариантов. Пусть НОД всех чисел a[1], a[2], ..., a[k] равен g. Тогда каждое число можно представить в виде a[i] = g × b[i], где b[i] — натуральное число. Если вынести g за скобки, получим g × (b[1] + b[2] + ... + b[k]) = n. Отсюда следует, что g должен быть делителем числа n. Значит, можно перебрать все делители n и для каждого проверить, сможем ли мы построить подходящую строго возрастающую последовательность b[1], b[2], ..., b[k]. Минимальная сумма k различных натуральных чисел достигается на последовательности 1, 2, ..., k, поэтому условие существования такое: k × (k + 1) / 2 ≤ n / g. Если это условие выполняется, выгоднее всего взять числа 1, 2, ..., k − 1, а весь оставшийся остаток добавить к последнему числу. При этом последовательность останется строго возрастающей. Значит, нам нужно найти максимальный делитель g числа n, для которого выполняется это условие, а затем восстановить ответ. В задаче есть ловушка ❣️: при k = 10^10 выражение k × (k + 1) / 2 уже переполняет 64-битный целочисленный тип, поэтому для сравнения в этой задаче удобно считать его в типе long double, ведь нам важны лишь порядок и лидирующие биты. исходный код решения на C++

🤩 В новом видео мы разбираем арифметику остатков: как устроены операции по модулю, что такое кольцо вычетов и как правильно брать остаток от деления отрицательных чисел. Рассматриваем алгоритм быстрого возведения в степень, реализуем его рекурсивно и нерекурсивно. Показываем, как деление по модулю сводится к умножению на обратный элемент, и выводим формулу его нахождения через малую теорему Ферма, решаем соответствующие задачи. видео на YouTube видео на Rutube видео во ВКонтакте

💚 В новом видео мы завершаем разбор задач на простые числа и решето Эратосфена. Учимся находить полные квадраты простых чисел, аккуратно вычислять целочисленный квадратный корень без ошибок вещественной арифметики, использовать решето Эратосфена для быстрых проверок на простоту и применять разложение на множители в задачах на делимость и делители. видео на YouTube видео на Rutube видео во ВКонтакте

Уже 15 мая в РТУ МИРЭА пройдёт мастер-класс «Введение в спортивное программирование» Расскажем про спортивное программирование, секцию РТУ МИРЭА и разберём несколько интересных задач. Если планируешь прийти, обязательно пиши @i_hate_foobar.

💚 Сегодня мы подробно разбираем решето Эратосфена: от мотивации и устройства до реализации на C++, оценки асимптотики и практических оптимизаций. Затем переходим к задачам и показываем, как использовать решето для поиска всех простых чисел, подсчёта количества делителей факториала, а также массовой факторизации множества чисел. видео на YouTube видео на Rutube видео во ВКонтакте

😄 В новом видео разбираем дерево отрезков: как оно устроено, чем отличается от корневой декомпозиции, как обрабатывает запросы на НОД, сумму и максимум. Реализуем его на C++ и добавляем поддержку операций над отдельными элементами: присваивание и прибавление. В конце смотрим, как Питер Фенвик радикально упростил дерево отрезков на сумму, выкинув ненужные узлы и перенумеровав оставшиеся, и получил структуру данных, которую позже назвали деревом Фенвика. видео на YouTube видео на Rutube видео во ВКонтакте

⏹️ Спешим к вам с расписанием занятий. Неделя обещает быть насыщенной — 15.05. ждём всех на мастер-классе «Введение в спортивное программирование»! 💕 ВТ, 12 мая: в 19:00 Zoom с Анатолием Игнатьевым. 💕 СР, 13 мая: в 21:00 Zoom с Дмитрием Козыревым. 💕 ЧТ, 14 мая: в 18:00 занятие в аудитории Г-423 с Андреем Ишутиным. 💕 ВС, 17 мая: в 21:00 Zoom с Дмитрием Козыревым. Если ты студент РТУ МИРЭА и планируешь прийти, обязательно пиши @i_hate_foobar.

Эти сложные задачи на сканирующую прямую слишком много о себе возомнили 🤠 В новом видео мы завершаем их разбор: ⏺️«C. Враждебные пары»: комбинаторно считаем количество подотрезков перестановки, не содержащих ни одной заданной пары элементов; ⏺️«D. Frets on Fire»: группируем запросы и обрабатываем их, поддерживая актуальный ответ и вовремя обновляя его; ⏺️«F. Вложенные отрезки»: считаем количество вложенных отрезков с помощью ordered_set. видео на YouTube видео на Rutube видео во ВКонтакте

🤩 В новом видео мы продолжаем изучать корневую декомпозицию и разбираем отложенные операции: как их накапливать, когда применять и как учитывать при вычислении функции на отрезке. На примерах задач «A. Прибавление и минимум» и «B. Умножение и сумма» адаптируем структуру данных под разные типы обновлений и запросов. В конце добавляем ещё один важный тип операций — поиск значения в корневой декомпозиции, начиная с заданной позиции. видео на YouTube видео на Rutube видео во ВКонтакте

👩‍🎓 Вот мы и добрались до разбора задачи «Пути в полном бинарном дереве». В ней дано полное бинарное дерево из n вершин, и нужно ответить на q запросов: для каждого из них смоделировать перемещение по дереву, начиная с заданной вершины, и определить, в какой вершине мы окажемся в конце. Пронумеруем уровни, на которых находятся вершины дерева, снизу вверх, от листьев к корню: 1, 2, 3, …, log₂(n + 1). Тогда на уровне k все вершины образуют арифметическую прогрессию: первый элемент — 2ᵏ⁻¹, шаг — 2ᵏ. Например, в дереве из условия: ➡️ уровень 4: 8; ➡️ уровень 3: 4, 12; ➡️ уровень 2: 2, 6, 10, 14; ➡️ уровень 1: 1, 3, 5, 7, 9, 11, 13, 15. Если известны текущий уровень currLevel и позиция currPos на нём, то переходы считаются так: ➡️ L: nextLevel = currLevel - 1, nextPos = currPos * 2; ➡️ R: nextLevel = currLevel - 1, nextPos = currPos * 2 + 1; ➡️ U: nextLevel = currLevel + 1, nextPos = currPos / 2. Для работы с такой нумерацией осталось реализовать две функции. Первая по номеру вершины находит её уровень и позицию на нём. Для этого перебираем все уровни и проверяем, принадлежит ли номер вершины арифметической прогрессии этого уровня: разница между ним и началом прогрессии должна делиться на шаг. Вторая по уровню и позиции восстанавливает номер вершины. Если такой вершины нет, возвращаем -1. После этого каждый запрос обрабатывается напрямую: идём вдоль строки, пытаемся сделать очередной переход и игнорируем его, если он невозможен. исходный код решения на C++ 🏋️‍♀️ Следующая задача — «Максимальный НОД». Снова конструктивы! Нужно составить последовательность a₁, a₂, ..., aₖ, состоящую из k натуральных чисел, такую, что их сумма равна n, а наибольший общий делитель максимален среди всех возможных вариантов. Соберём очередную головоломку в среду, 20 мая.

👩‍🎓 Вот мы и добрались до разбора задачи «Пути в полном бинарном дереве». В ней дано полное бинарное дерево из n вершин, и нужно ответить на q запросов: для каждого из них смоделировать перемещение по дереву, начиная с заданной вершины, и определить, в какой вершине мы окажемся в конце. Пронумеруем уровни, на которых находятся вершины дерева, снизу вверх, от листьев к корню: 1, 2, 3, …, log₂(n + 1). Тогда на уровне k все вершины образуют арифметическую прогрессию: первый элемент — 2ᵏ⁻¹, шаг — 2ᵏ. Например, в дереве из условия: ➡️ уровень 4: 8; ➡️ уровень 3: 4, 12; ➡️ уровень 2: 2, 6, 10, 14; ➡️ уровень 1: 1, 3, 5, 7, 9, 11, 13, 15. Если известны текущий уровень currLevel и позиция currPos на нём, то переходы считаются так: ➡️ L: nextLevel = currLevel - 1, nextPos = currPos * 2; ➡️ R: nextLevel = currLevel - 1, nextPos = currPos * 2 + 1; ➡️ U: nextLevel = currLevel + 1, nextPos = currPos / 2. Для работы с такой нумерацией осталось реализовать две функции. Первая по номеру вершины находит её уровень и позицию на нём. Для этого перебираем все уровни и проверяем, принадлежит ли номер вершины арифметической прогрессии этого уровня: разница между ним и началом прогрессии должна делиться на шаг. Вторая по уровню и позиции восстанавливает номер вершины. Если такой вершины нет, возвращаем -1. После этого каждый запрос обрабатывается напрямую: идём вдоль строки, пытаемся сделать очередной переход и игнорируем его, если он невозможен. исходный код решения на C++ 🏋️‍♀️ Следующая задача — «Максимальный НОД». Снова конструктивы! Нужно составить последовательность a₁, a₂, ..., aₖ, состоящую из k натуральных чисел, такую, что их сумма равна n, а наибольший общий делитель максимален среди всех возможных вариантов. Соберём очередную головоломку в среду, 20 мая.

🌕 Сегодня мы разбираемся с задачами квалификационного этапа Чемпионата Тулы 2026. Контест получился довольно разнообразным: здесь есть как простая геометрия, так и жадные алгоритмы, битовые операции и XOR, лексикографическая сортировка структур и последовательностей. А ещё математика и формулы, моделирование процессов, подсчёт троек чисел, задачи на наблюдение и поиск закономерностей, бинарный поиск и динамическое программирование. видео на YouTube видео на Rutube видео во ВКонтакте

❤️ В новом видео мы приступаем к изучению теории графов и проходим основные понятия, определения, свойства и виды графов, способы их представления. Кроме того, разбираем пару базовых задач из раздела EDU на codeforces. видео на YouTube видео на Rutube видео во ВКонтакте

Ну что, в бой с новыми силами? Ждём тебя на наших занятиях по спортивному программированию! ✨ ВТ, 5 мая: в 18:00 занятие в аудитории Г-423 с Андреем Ишутиным. ✨ ВТ, 5 мая: в 19:00 Zoom с Анатолием Игнатьевым. ✨СР, 6 мая: в 21:00 Zoom с Дмитрием Козыревым. ✨ ВС, 10 мая: в 21:00 Zoom с Дмитрием Козыревым. Если ты студент РТУ МИРЭА и планируешь прийти, обязательно пиши @i_hate_foobar.

🟣 В новом видео продолжаем разбирать задачи на бинарный поиск по ответу, включая вещественный поиск по времени и расстоянию. Показываем, как зафиксировать ответ и эффективно проверить, подходит ли он, а затем переходим к более сложным применениям: в графе минимизируем максимум на пути, а в массиве ищем отрезок с максимальным средним. видео на YouTube видео на Rutube видео во ВКонтакте