План на сегодня

Сегодняшняя тренировка

Индивидуальный план тренировки, сформированный AI-тренером на основе вашего уровня и пробелов в теме префиксных сумм и структур данных.

Загрузка плана...

Часть 1: Pattern Recognition Рекомендуемое время: 5 мин

Быстрое распознавание паттерна

Определите необходимый алгоритм по описанию задачи без написания полноценного кода. Тренирует алгоритмическую интуицию.

Задача: "Компоненты при добавлении ребер"

Дано пустое неориентированное граф-множество из N вершин. Поступают Q запросов двух типов: добавить ребро между u и v, и узнать количество связных компонент в графе на данный момент. Все операции нужно делать эффективно в режиме реального времени.

Вердикт AI-тренера

Часть 2: Написание решения Рекомендуемое время: 15-20 мин

Решение задачи: Суммы на отрезках

Напишите законченное, оптимальное по памяти и времени решение. Программа должна считывать данные из стандартного потока ввода.

Задача: "Суммы на отрезках (Range Sum Query)"

Дано массив a из n чисел и q запросов. Каждый запрос представляет собой пару индексов (l, r) (1-индексация). Для каждого запроса выведите сумму элементов от l до r включительно. Сложность на запрос должна быть O(1).

AI Анализ Решения

Вердикт:

Часть 3: Скоростной спринт Рекомендуемое время: 5 мин

Спринт шаблона: DSU (СНМ)

Реализуйте классический шаблон структуры данных СНМ (Disjoint Set Union) с эвристиками сжатия путей и ранговой оптимизацией на память. Ошибки недопустимы.

Реализация DSU класса (Python)

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [1] * n

    def find(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i != root_j:
            if self.rank[root_i] < self.rank[root_j]:
                root_i, root_j = root_j, root_i
            self.parent[root_j] = root_i
            if self.rank[root_i] == self.rank[root_j]:
                self.rank[root_i] += 1

Спринт-проверка