Разбор задач Educational Codeforces Round 10

Правка ru6, от Edvard, 2016-03-27 16:03:35

652A - Gabriel and Caterpillar

Задача предложена пользователем unprost.

Рассмотрим три случая.

  1. h1 + 8a ≥ h2 — в этом случае Гусеница заберётся на яблоко тот же день, поэтому ответ равен 0.

  2. Первое условие не выполнено и a ≤ b — в этом случае гусеница никогда не сможет забраться на яблоко, поскольку она это не сделает в первый день, а после каждой ночи она будет оказываться ниже начала прошлого дня.

  3. Если первые два условия не выполнены, легко видеть, что ответ равен .

Решение на С++

Также эту задачу можно было сдать простым моделированием, поскольку высоты и скорости были небольшими.

Сложность: O(1).

652B - z-sort

Задача предложена пользователем Smaug.

Легко видеть, что для любого массива можно осуществить z-сортировку. Пусть в массиве всего чётных позиций. Тогда можно на этих позициях расставить наибольшие k элементов массива. Очевидно после этого массив окажется z-отсортированным.

Решение на C++

Сложность: O(nlogn).

652C - Foe Pairs

Эта одна из задач предложенных пользователями Bayram Berdiyev bayram, Allanur Shiriyev Allanur, Bekmyrat Atayev Bekmyrat.A.

Предподсчитаем сначала для каждого числа x его позицию posx в перестановке. Это легко сделать за линейное время. Теперь рассмотрим некоторую враждебную пару (a, b) (можно считать, что posa < posb). Запомним для каждого числа a самую левую позицию posb такую, что (a, b) образуют враждебную пару. Обозначим эту величину za. Теперь будем идти по перестановке справа налево и поддерживать позицию rg наибольшего корректного интервала с левым концом в текущей позиции перестановки lf. Значение rg пересчитывается следующим образом: rg = min(rg, z[lf]). Соответсвенно к ответу на каждой итерации нужно прибавлять величину rg - lf + 1.

Решение на C++

Сложность: O(n).

652D - Nested Segments

Задачу предложил Алексей Дергунов dalex.

Эта задача является стандартной двумерной задачей, которая решается с помощью одномерной структуры данных. Абсолютно аналогично решаются многие другие задачи (например, поиск наибольшей по весу цепочки точек на плоскости такой, что у каждой следующей точки обе координаты больше, чем у предыдущей). Запишем задачу формально для всех i нам нужно посчитать, количество индексов j, что выполнены следующие условия: ai < aj и bj < aj. Отсортируем все отрезки по левому концу справа налево. И в некоторой структуре данных (удобнее всего здесь использовать дерево Фенвика) будем поддерживать правые концы уже обработанных отрезков (с большим левым концом, чем у текущего отрезка). Тогда для текущего отрезка ответом является сумма на префиксе его правого конца.

Таким образом, от одной размерности задачи (от условия ai < aj) мы избавились с помощью сортировки и обработки отрезков справа налево. А от второй размерности (условия bj < aj) мы избавились использованием структуры данных (взятием суммы на префиксе).

Решение на C++

Сложность: O(nlogn).

652E - Pursuit For Artifacts

Задачу предложил Алексей Дергунов dalex.

Компонентой рёберной двусвязности в неориентированном графе называется наибольшее по включению множество вершин такой, что между любой парой вершин существует два рёберно-неперескающихся пути. Рассмотрим граф в котором вершинами являются компоненты рёберной двусвязности исходного графа. Легко видеть, что этот граф является деревом (если бы в нём был цикл, то компоненты цикла образовывали бы одну компоненту двусвязности). Поскольку рёбра исходного графа разрушаются после прохождения по ним, мы не можем перейдя по ребру этого дерева вернуться назад (поскольку это дерево).

Рассмотрим компоненты двусвязности в которые попали вершины a и b. Обозначим их A и B. Утверждение: ответ YES если и только, если на пути в дереве между вершинами A и B либо есть ребро дерева с артефактом, либо есть компонента содержащая внутри себя ребро с артефактом. Легко видеть, что утверждение верно: если такое ребро есть, то мы либо пройдём по нему пока будем идти по дереву из A в B, либо можем пройти по нему внутри компоненты (ведь внутри компоненты между каждой парой вершин есть два рёберно-непересекающихся пути). Обратное также легко непосредственно проверить.

Одним из способов выделить компоненты рёберной двусвязнсти является следующий:

  1. Ориентируем исходный неориентированный граф по обходу в глубину (для каждого ребра запомним в каком направлении мы впервые захотели пройти по нему).

  2. Выделим в этом ориентированном графе компоненты сильной связности.

Утверждение: компоненты сильной связности нового графа будут совпадать с компоненты рёберной двусвязности исходного графа.

Также в этой задаче можно было заметить, что рёбрами дерева будут мосты (мосты в смысле теории графов, а не легенды из условия). Поэтому для решения задачи достаточно выделить мосты в графе.

Некороткое решение на C++

Сложность: O(n + m).

652F - Ants on a Circle

Задача предложена пользователем Lewin Gan Lewin.

Наблюдение 1: если для нас муравьи неразличимы, можно считать, что никаких столкновений не происходит, а муравьи просто проходят друг через друга. Таким образом, мы можем легко узнать положения всех муравьёв в конце, но мы не можем сказать какой муравей где находится.

Наблюдение 2: относительный порядок муравьёв никогда не меняется.

Таким образом для решения задачи нам достаточно определить положения хотя бы одного муравья по прошествии t единиц времени.

Будем решать эту задачу следующим образом:

  1. Рассмотрим положения муравьёв по прошествии m единиц времени. Легко видеть согласно первого наблюдения, что положения муравьёв остнутся исходными, но порядок изменится (произойдёт циклический сдвиг порядка). Найдём этот циклический сдвиг sh и применим его раз.

  2. После этого останется единиц времени.

Таким образом, задача свелась к тому, чтобы промоделировать процесс для одного муравья за время m и за время . Заметим, что за промежуток времени не больший m один фиксированный муравей не может столкнуться с другим муравьём более двух раз. Таким образом, если мы будем игнорировать столкновения всех остальных муравьёв кроме фиксированного всего произойдёт не более 2n столкновений.

Давайте моделировать этот процесс с помощью двух очередей муравьёв идущих влево и вправо. Каждый раз мы должны брать в очереди противоположного направления первого муравья, обрабатывать столкновение и кидать его в конец очереди другого направления.

Подсказка: если у вас возникнут проблемы со случаем, когда муравей может попасть в две позиции, просто промоделируйте процес со следующим муравьём.

Решение на C++

Сложность: O(nlogn).

Теги учебный раунд 10, разбор задач

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en10 Английский Edvard 2016-04-27 18:10:38 50 Tiny change: 'on $b_j < b_j$ is hol' -> 'on $b_j < a_j$ is hol'
en9 Английский Edvard 2016-03-27 16:06:27 50 Tiny change: 'xity: $O(n)$.\n\n###' -> 'xity: $O(n+m)$.\n\n###'
ru7 Русский Edvard 2016-03-27 16:06:01 50 Мелкая правка: 'ость: $O(n)$.\n\n###' -> 'ость: $O(n+m)$.\n\n###'
en8 Английский Edvard 2016-03-27 16:03:49 52 Tiny change: 'se and $a > b$ &mdash' -> 'se and $a \le b$ &mdash'
ru6 Русский Edvard 2016-03-27 16:03:35 52 Мелкая правка: 'нено и $a > b$ &mdash' -> 'нено и $a \le b$ &mdash'
ru5 Русский Edvard 2016-03-27 15:58:06 51 Мелкая правка: 'ac{h_2-h_1}{12(a-b)}' -> 'ac{h_2-h_1-8a}{12(a-b)}'
en7 Английский Edvard 2016-03-27 15:56:28 51 Tiny change: 'ac{h_2-h_1}{12(a-b)}' -> 'ac{h_2-h_1-8a}{12(a-b)}'
ru4 Русский Edvard 2016-03-26 22:10:56 195
en6 Английский Edvard 2016-03-26 22:07:39 4829
en5 Английский Edvard 2016-03-26 21:54:41 44 Tiny change: 'mary="Not short C++' -> 'mary="Not too short C++'
en4 Английский Edvard 2016-03-26 21:52:57 3626
ru3 Русский Edvard 2016-03-26 21:43:57 50 Мелкая правка: '\n2. Первой условие н' -> '\n2. Первое условие н'
en3 Английский Edvard 2016-03-26 21:43:25 1057
en2 Английский Edvard 2016-03-26 21:37:54 62
en1 Английский Edvard 2016-03-26 13:36:55 4497 Initial revision for English translation
ru2 Русский Edvard 2016-03-26 13:32:24 13014 Мелкая правка: 'за время $r\mod m$. З' -> 'за время $t\mod m$. З' (опубликовано)
ru1 Русский Edvard 2016-03-25 17:00:25 1081 Первая редакция (сохранено в черновиках)