Сборник Олпрогера

Также публикуем достаточно полезный лонгрид, в котором вы сможете понять, как надо было думать над задачами

А:
Давайте попробуем исходную рассадку сделать симметричной. В целом понятно, что любая расстановка должна содержать эту рассадку, как подмножество. Дальше уже можно просто добавлять пассажиров парами в две свободные симметричные клетки.
Б:
Назовем элемент B_i центральным, где знаки меняются. Понятно, что в битонической последовательности центральный элемент ровно один. Поэтому давайте переберем какой элемент будет центральным и найдем самый дальний возможный левый конец и аналогично самый дальний возможный правый конец (это можно сделать многими способами - это стандартная задача). назовем их L и R. Достаточно понятно, что начало битонической последовательности, где ее центральный элемент на позиции i может начаться на позиции L и вплоть до i. Аналогично с R. Очевидно, что количество таких последовательностей является произведением количества валидных левых и правых концов. Задача решается из соображений, что нам удобно перебрать и как склеить два независимых конца.
C:
Заметим, что на самом деле порядок удаления строк и столбцов нам не важен. Мы можем заранее выбрать какие удалим строки и какие строки и найти сумму получившейся подматрицы. Давайте рассмотрим 2 ^ h вариантов, какие мы удалим строки. Теперь в получившейся матрице нужно выбрать такое подмножество столбцов, что их сумма = s. Это стандартная задача на рюкзак, которую можно решать разными способами. В данном случае нам будет удобен способ, использующий метод Meet in the middle, который найдет такой способ за 2 ^ (w / 2). Итого мы получаем решение за 2 ^ h * 2 ^ (w / 2), что должно получать полный балл.
Задача требует два наблюдения: порядок на самом деле не важен и умение решать задачу о рюкзаке таким способом.
Д:
Первая же идея в задаче - это бинпоиск по ответу. Давайте рассмотрим самую дальнюю вершину от корня, если ее расстояние <= h (что мы перебираем в бинпоиске), то мы добились нужного. Иначе мы должны какого - то ее предка прикрепить к корню. В целом понятно, что самый лучший из таких - это на предок на расстоянии h - 1 от вершины (найти это вершину можно, как h - 1 вершину на пути от v до root, где root - текущий корень, что можно искать с помощью бинарных подъемов). Мы можем мысленно поддерево это вершины удалить, так как все ее потомки также имеют расстояние <= h. Продолжим процесс, пока число возможных ребер, которые можно добавить не кончится. Как это аккуратно поддерживать? Воспользуемся популярной идей. Давайте запишем обход дерева в массив, подвесив ее за вершину 0. tin[v] - время входа в вершину, а tout[v] - время выхода. Тогда все вершины поддерева имеют индекс в массиве id >= tin[v] && id <= tout[v] (то есть все лежат на некотором отрезке в массиве обхода). Тогда для root = 0, уменьшить расстояние в поддереве можно с помощью прибавления на отрезке на построенном дереве отрезке, а искать самую дальнюю вершину с помощью max на всем массиве. Как не перестраивать это дерево отрезков для различных корней? Тут удобно будет заметить, что на самом деле нужно прибавить число на всем массиве и вычесть в поддереве, в котором лежит новый корень в исходно подвешенном поддереве (рекомендую самому подумать, почему такой метод действительно работает). Это поддерево легко можно найти с помощью бинпоиска. Склеивая все эти идеи, мы получаем решение, которое работает за N * K * log^2(N). Это уже может зайти, если это аккуратно написать. Заметим интересную идею, ответ для вершины соседней по ребру в дереве отличается не более чем на 1. Давайте искать ответ для вершин в порядке обхода дфс к примеру и проверять только ans, ans - 1, ans + 1. Таким образом, мы избавились от большого количества бинпоисков (достаточно запустить его только одной вершины). И получаем решение за NK * log(N). Задача требует небольшого анализа над тем, как устроен ответ и умение использовать структуры данных для деревьев.

Автор: Александр Сушин

👍57👎6

www.tgoop.com/sbornik_olprog/168

3.73K viewsNikolay Khadzakos, Jan 20, 2024 at 13:31

Также публикуем достаточно полезный лонгрид, в котором вы сможете понять, как надо было думать над задачами

А:
Давайте попробуем исходную рассадку сделать симметричной. В целом понятно, что любая расстановка должна содержать эту рассадку, как подмножество. Дальше уже можно просто добавлять пассажиров парами в две свободные симметричные клетки.
Б:
Назовем элемент B_i центральным, где знаки меняются. Понятно, что в битонической последовательности центральный элемент ровно один. Поэтому давайте переберем какой элемент будет центральным и найдем самый дальний возможный левый конец и аналогично самый дальний возможный правый конец (это можно сделать многими способами - это стандартная задача). назовем их L и R. Достаточно понятно, что начало битонической последовательности, где ее центральный элемент на позиции i может начаться на позиции L и вплоть до i. Аналогично с R. Очевидно, что количество таких последовательностей является произведением количества валидных левых и правых концов. Задача решается из соображений, что нам удобно перебрать и как склеить два независимых конца.
C:
Заметим, что на самом деле порядок удаления строк и столбцов нам не важен. Мы можем заранее выбрать какие удалим строки и какие строки и найти сумму получившейся подматрицы. Давайте рассмотрим 2 ^ h вариантов, какие мы удалим строки. Теперь в получившейся матрице нужно выбрать такое подмножество столбцов, что их сумма = s. Это стандартная задача на рюкзак, которую можно решать разными способами. В данном случае нам будет удобен способ, использующий метод Meet in the middle, который найдет такой способ за 2 ^ (w / 2). Итого мы получаем решение за 2 ^ h * 2 ^ (w / 2), что должно получать полный балл.
Задача требует два наблюдения: порядок на самом деле не важен и умение решать задачу о рюкзаке таким способом.
Д:
Первая же идея в задаче - это бинпоиск по ответу. Давайте рассмотрим самую дальнюю вершину от корня, если ее расстояние <= h (что мы перебираем в бинпоиске), то мы добились нужного. Иначе мы должны какого - то ее предка прикрепить к корню. В целом понятно, что самый лучший из таких - это на предок на расстоянии h - 1 от вершины (найти это вершину можно, как h - 1 вершину на пути от v до root, где root - текущий корень, что можно искать с помощью бинарных подъемов). Мы можем мысленно поддерево это вершины удалить, так как все ее потомки также имеют расстояние <= h. Продолжим процесс, пока число возможных ребер, которые можно добавить не кончится. Как это аккуратно поддерживать? Воспользуемся популярной идей. Давайте запишем обход дерева в массив, подвесив ее за вершину 0. tin[v] - время входа в вершину, а tout[v] - время выхода. Тогда все вершины поддерева имеют индекс в массиве id >= tin[v] && id <= tout[v] (то есть все лежат на некотором отрезке в массиве обхода). Тогда для root = 0, уменьшить расстояние в поддереве можно с помощью прибавления на отрезке на построенном дереве отрезке, а искать самую дальнюю вершину с помощью max на всем массиве. Как не перестраивать это дерево отрезков для различных корней? Тут удобно будет заметить, что на самом деле нужно прибавить число на всем массиве и вычесть в поддереве, в котором лежит новый корень в исходно подвешенном поддереве (рекомендую самому подумать, почему такой метод действительно работает). Это поддерево легко можно найти с помощью бинпоиска. Склеивая все эти идеи, мы получаем решение, которое работает за N * K * log^2(N). Это уже может зайти, если это аккуратно написать. Заметим интересную идею, ответ для вершины соседней по ребру в дереве отличается не более чем на 1. Давайте искать ответ для вершин в порядке обхода дфс к примеру и проверять только ans, ans - 1, ans + 1. Таким образом, мы избавились от большого количества бинпоисков (достаточно запустить его только одной вершины). И получаем решение за NK * log(N). Задача требует небольшого анализа над тем, как устроен ответ и умение использовать структуры данных для деревьев.

Автор: Александр Сушин

BY Сборник Олпрогера