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

👨‍💻 Сегодня разберём задачу «Максимальный НОД». В ней нужно построить строго возрастающую последовательность 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 видео во ВКонтакте

Сегодня в 17:35 состоится Codeforces Round 1096 (Div. 3) 🤓 Контест будет рейтинговым для начинающих — участников третьего дивизиона. Формат такой: 8 задач и 2,5 часа на их решение. узнать подробности 🔴 участвовать 🔴

В новом видео мы продолжаем изучать теорию чисел ❤️ Рассматриваем, как: • получить все делители и найти k-й среди них (без сортировки); • проверить, что число n представимо в виде p² × q; • корректно извлечь квадратный корень из очень большого числа порядка 9 × 10¹⁸. А ещё разбираем несколько интересных олимпиадных задач на поиск делителей, факторизацию и математические наблюдения. видео на YouTube видео на Rutube видео во ВКонтакте

🔮 Сегодня мы разберём одну из самых мистических задач с сайта codeforces — «Магический нечётный квадрат». Нам даны натуральные числа от 1 до n², где n — нечётное число. Требуется расположить их в клетках квадрата n × n так, чтобы в каждой строке, каждом столбце и на обеих главных диагоналях сумма была нечётной. Первое, на что стоит обратить внимание в условии: нам дают только нечётные n. Почему? Чтобы это выяснить, давайте посчитаем, сколько у нас чётных и нечётных чисел. Так как n нечётно, n² тоже нечётно, а поскольку числа от 1 до n² чередуются по чётности, нечётных будет на 1 больше. Значит, чётных чисел (n² − 1) / 2, а нечётных — (n² + 1) / 2. Рассмотрим ромб в исходном квадрате: в нём (n² + 1) / 2 клеток. Столько же у нас и нечётных чисел. Совпадение⁉️ Поставим все наши нечётные числа в ромб, а чётные — за его пределы, и проверим, что магические условия задачи выполняются. В каждой строке и каждом столбце ромб занимает нечётное число клеток, поэтому и нечётных чисел там будет нечётное количество, а значит, сумма окажется нечётной. Диагонали проще всего проверить через симметрию. Центр лежит на диагонали, а для каждой другой клетки ромба найдётся симметричная ей клетка. Поэтому таких клеток нечётное количество и сумма снова будет нечётной. Вот мы и решили головоломку, построив магический нечётный квадрат! исходный код решения на C++ 🔎 Следующая задача — «Пути в полном бинарном дереве». В ней дано полное бинарное дерево из n вершин, и нужно ответить на q запросов: для каждого из них промоделировать перемещение по дереву, начиная с заданной вершины, и определить, в какой вершине мы окажемся в конце. Основная сложность в том, что n может быть очень большим — вплоть до 10¹⁸, так что строить дерево явно уже не получится. Удачи! Обойдём это дерево в следующую среду, 6 мая.

В РТУ МИРЭА пройдёт мастер-класс «Введение в спортивное программирование» Когда: 15 мая в 18:00 Где: проспект Вернадского, 78, аудитория А-1 На мастер-классе расскажем: ➡️ что такое спортивное программирование и зачем им заниматься; ➡️ чем живёт секция спортивного программирования РТУ МИРЭА; ➡️ каких результатов мы уже добились и что планируем дальше. И, конечно, мы разберём несколько интересных и доступных олимпиадных задач. 💙 Приглашаем всех студентов РТУ МИРЭА. Приходите, чтобы открыть для себя новые грани программирования!

⚡️ Студенты РТУ МИРЭА приняли участие в командном турнире 10-го Открытого Чемпионата Юга России ContestSFedU-2026 ⚡️ Финальный этап турнира по программированию прошёл в солнечном городе Таганрог, где 26 апреля встретились 50 сильнейших команд, чтобы побороться за призовые места. Все они успешно прошли отборочный этап, но теперь им предстояло решить 14 задач за 5 часов. 💍 Кривосудов Роман и Исаков Эдуард справились с 7-ю задачами и заняли 13-е место, остановившись в шаге от призовой зоны. Айсин Эльдар, Чебаков Александр и Николаев Иван решили 4 задачи и застолбили за собой медиану в турнирной таблице. Поздравляем ребят и ждём, пока организаторы опубликуют фотографии в своей группе ВКонтакте.