Всем привет! Несколько часов назад прошел TeamsCode турнир. Я хочу сделать разбор задач ABCDEF, которые я смог решить/понять.
Ссылка на задачу: (ссылка на ABCDEF A)
Идея решения: Нужно полностью покрыть все квадраты. Простое решение — выбрать максимально возможный квадрат.
Алгоритм:
- Берем квадрат с координатами (-10^9, 10^9, -10^9, 10^9).
- Этот квадрат гарантированно покрывает все поле.
Вывод: задача решается выбором максимального квадрата.
Ссылка на задачу: (ссылка на ABCDEF B)
Идея решения: Найти MEX всех слоев. Условие: числа i и i+1 не должны находиться в одном узле с i.
Алгоритм:
- Создаем мап mp, где для каждого числа хранится слой, в котором оно находится.
- Создаем массив vis для отслеживания, какие слои уже использованы.
- Инициализируем MEX = 1.
- Если слой числа MEX еще не посещен, увеличиваем MEX, отмечаем слой как посещенный и продолжаем.
- Иначе увеличиваем MEX и заканчиваем цикл.
Вывод: MEX после выполнения алгоритма — искомый минимальный исключающий элемент.
Ссылка на задачу: (ссылка на ABCDEF C)
Идея решения: Определяем f(x) — сумму a[i] в поддереве x.
Алгоритм:
- С помощью DFS или BFS считаем f(x) для всех узлов x от 1 до n.
- Создаем массив cnt. Для каждого i добавляем f[i] / a[i]. Это как максимальное число k, такое что k * sm <= cnt[i], где sm — исходная сумма массива a.
- Сортируем массив cnt и выводим sm * cnt[i] для всех i.
Вывод: получаем суммы поддеревьев для всех узлов.
Ссылка на задачу: (ссылка на ABCDEF D)
Идея решения: Алиса может выбрать исходное a[i] или уже измененное значение, чтобы минимизировать сумму после хода Боба.
Алгоритм:
- Создаем три массива:
- a[i] = (v[i] | x) — v[i] — вклад Алисы.
- b[i] = (v[i] & y) — v[i] — вклад Боба.
- c[i] = ((v[i] | x) & y) — v[i] — вклад Боба после изменения Алисы.
- Находим два максимума для массива Боба (b[i] и c[i]). Если c[i] равен максимуму, берём другой максимум.
- Считаем сумму s = a[i] + sum + max(c[i], val).
- Ответ — минимальное значение s среди всех i.
Вывод: таким образом Алиса минимизирует итоговую сумму.
Ссылка на задачу: (ссылка на ABCDEF E)
Идея решения: Определяем максимальный индекс тележки, который можно отправить, не столкнувшись с коровой.
Алгоритм:
- Если какой-то рельс пуст, ответ — min(a, b).
- Иначе ищем максимальный индекс коровы, такой что x<=a[pos] или x <= b[pos], где x — максимальная тележка.
- Если такая корова есть на обоих рельсах, берём левую самую первую позицию: min(a — pos1, b — pos2).
- Если корова есть только на одном рельсе, выбираем индекс для этого рельса.
Вывод: получаем максимальный индекс тележки, который можно безопасно отправить.
Ссылка на задачу: (ссылка на ABCDEF F)
Идея решения: Проверяем корректность операций над массивом.
Алгоритм:
- Элемент a[3] встречается во всех типах операций, поэтому он критичен.
- Ответ не существует, если выполняется любое из условий:
- a[3] — a[2] < 0
- a[3] — a[4] < 0
- a[1] — a[3] + a[4] < 0
- a[2] — a[3] + a[5] < 0
- a[3] — a[1] — a[5] < 0
- Иначе ответ — сумма всех элементов минус количество операций: a[1] + a[2] + a[4] + a[5] — a[3].
Вывод: проверяем критические условия для a[3] и получаем итоговую сумму.
