405A - Переключение гравитации

Заметим, что в конечном расположении все высоты столбиков расположены в неубывающем порядке. Также, количество столбиков каждой высоты остаётся неизменным. Это означает, что ответом является упорядоченная последовательность данных высот столбиков.

Сложность решения: O(n), так как можно упорядочить подсчётом.

405B - Эффект домино

Если самая первая толкнутая доминошка слева была толкнута влево на позиции l, все доминошки на префиксе [1;l] падают, иначе пусть l будет 0. Аналогично, если самая последняя толкнутая доминошка была толкнута направо на позиции r, все доминошки на суффиксе [r;n] падают, иначе пусть r будет n + 1. Теперь, на отрезке (l;r) остаются вертикально стоящие доминошки, а также блоки домино, поддерживающиеся одинаковыми силами с обеих сторон.

Когда доминошка на позиции p на отрезке (l, r) остаётся стоять вертикально? В одном случае, её не толкает ни одна другая доминошка. Это можно легко проверить, посмотрев на ближайшие к p толкнутые доминошки (с обеих сторон). Она была затронута другими домино, если самая близкая толкнутая доминошка слева была толкнута направо и самая близкая толкнутая доминошка справа была толкнута влево. Допустим, эти доминошки находятся на позициях x и y, x < p < y. Тогда, единственная возможность для доминошки остаться вертикально тогда, когда она находится в центре блока [x;y], что можно проверить выражением .

Сложность решения: O(n) / O(n²), что зависит от реализации.

406A - Необычное произведение

Если записать в виде формулы искомое произведение в задаче, получаем

Допустим, что i ≠ j. Тогда сумма содержит слагаемые A_ijA_ji и A_jiA_ij. Так как сумма всегда берётся по модулю 2, вместе эти слагаемые дают 0 к сумме. Из этого следует, что выражение всегда равняется сумме битов на диагонали:

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

Сложность решения: O(n + q), если не брать во внимание ввод... :)

406B - Игрушечная сумма

Определим для числа k его симметричное число как s + 1 - k. Так как в задаче s чётное число, k ≠ s - k.

Заметим, что (k - 1) + (s + 1 - k) = s, т.е., сумма числа и его симметричного всегда равно s. Будем обрабатывать все числа x множества X по порядку. Различаем два случая:

1. Если симметричное x не принадлежит X, добавим его к Y. Оба числа дают одинаковые значения к соответствующим суммам: x - 1 = s - (s + 1 - x).
2. Симметричное x принадлежит X. Тогда возьмём любое y такое, что ни y, ни симметричное y не принадлежат X, и добавим их к Y. Обе пары дают одинаковые значения к соответствующим суммам, а именно s.

Как доказать, что во втором случае мы всегда сможем найти такое y? Пусть количество симметричных пар, которые были обработаны в первом случае, равно a, тогда остаются других пар. Среди них, для пар оба числа принадлежат X, а для других пар никакие из чисел не принадлежат X. Чтобы выбрать такое что количество пар для Y, как и в X, должно выполняться

что равносильно , как и дано в условии.

Сложность решения: O(s) / O(n).

406C - Разрез графа

Можно доказать, что только графы с нечётным количеством рёбер нельзя разбить на пути длины 2. Мы построим рекурсивную функцию, решающую задачу, которая и будет служить доказательством этого утверждения.

Функция partition(v) будет работать на незаблокированных рёбрах. Она разбивает компоненту вершины v, связную по незаблокированным рёбрам, на пути длины 2. Если компонента имеет нечётное количество рёбер, функция разобьёт все рёбра компоненты, кроме одного ребра (u, v); тогда функция вернёт вершину u, ожидая, что предыдущий вызов функции присвоит это ребро какому-нибудь пути.

Функция работает следующим образом: найдём все вершины, соседние с v по незаблокированным рёбрам, назовём это множество adjacent. Далее заблокируем все рёбра из этих вершин в v. Для каждой u в adjacent, вызовем partition(u). Допустим, что вызов partition(u) вернул вершину w. Это значит, что мы можем присвоить её в путь (v, u, w). Иначе, если partition(u) ничего не вернул, добавим u к unpaired, потому что ребро (v, u) ещё не присвоено ни одному пути. Мы можем объединить в путь любые две вершины этого множества u, w в один путь (u, v, w). Спарим как можно больше таких вершин в любом порядке. Если из этого множества осталась только одна вершина, u, то функция вернёт u. В противном случае функция ничего не возвращает.

Функцию можно реализовать всего одним DFS:

partition(v) :
    adjacent = { u | not blocked[(u,v)] }
    for(u : adjacent)
        blocked[(u,v)] = true

    unpaired = {}
    for(u : adjacent)
        int w = partition(u)
        if(w = 0)
            add(unpaired, u)
        else
            print(v,u,w)

    while(size(unpaired) >= 2)
        int u = pop(unpaired)
        int w = pop(unpaired)
        print(u,v,w)

    if(not empty(unpaired))
        return pop(unpaired)
    else
        return 0

Сложность решения: O(n + m).

406D - Скалолазание

Заметим, что каждый путь скалолаза выпуклый в любом случае. Проведём пути из всех скал до последней скалы. Тогда эти пути образуют дерево с «корнем» в вершине последней скалы. Мы можем применить алгоритм Грэхема справа налево, чтобы найти рёбра этого дерева. Каждое удаление и добавление в стеке соответствует ровно одному ребру в дереве.

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

Сложность решения: .

406E - Тройки Хемминга

Давайте рассмотрим хэммингов граф из всех различных 2n строк, где каждые две строки соединены ребром длины, равному расстоянию Хэмминга между этими строками. Мы можем заметить, что этот граф обладает годным свойством: если упорядочить все вершины циклически по правильному 2n-угольнику со стороной длины 1, расстояние Хэмминга для каждых двух строк равняется длине кратчайшего пути между этими вершинами на периметре этого многоугольника.

Например, на рисунке изображён такой граф для n = 3. Серые рёбра имеют длину 1, оранжевые рёбра имеют длину 2, синие рёбра имеют длину 3. Это равняется соответствующему расстоянию Хэмминга.

Теперь, мы можем преобразовать каждую строку, закодированную парой чисел (s, f), в целое число (f + 1)·n - s. Новые числа будут среди 0, 1, ..., 2n - 1 и соотноситься с тем же циклическим порядком на периметре многоугольника. Данные строки переходят в какой-то набор вершин. Теперь нам нужно найти количество треугольников (возможно, дегенерированных) с наибольшим периметром в этом подграфе. Далее будет полезно упорядочить преобразованные числа.

Для начала, можно попробовать понять, каким может быть этот периметр. Если существует такой диаметр в полном графе, что все данные точки находятся по одну сторону диаметра, периметр будет равен 2d, где d является значением самого длинного ребра:

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

Если для любого диаметра это не выполняется, тогда наибольший периметр равен 2n. Это можно доказать, взяв две различных точки a, b, и проведя два диаметра из этих точек как концов; так как это не предыдущий случай, должна быть третья точка c в месте, где периметр треугольника a, b, c равняется 2n.

Самая хитрая часть и есть посчитать тройки в этом случае. Мы делаем это, работая с диаметром (0, n). Всего может быть несколько случаев:

1. Наибольший треугольник содержит обе вершины 0 и n. Это простой случай: с любой другой вершиной как третьей такой треугольник имеет периметр 2n.
2. Наибольший треугольник содержит вершину 0, но не n. Тогда вторая вершина должна находится на отрезке [0, n), а третья на отрезке (n + 1, 2n - 1], и расстояние по часовой стрелке между второй и третьей вершинами не должно превышать n (в противном случае периметр треугольника был бы меньше, чем 2n). Мы считаем количество таких троек, двигая два указателя (по одному на каждый из этих отрезков). Для каждого указателя в первом отрезке, все точки, начиная с n + 1 до второго указателя образуют наибольший треугольник. Аналогично мы решаем случай, когда треугольник содержит n, но не 0.
3. Наибольший треугольник не содержит ни 0, ни n как вершины. Тогда одна вершина треугольника должна находится на одной стороне диаметра (0, n), а две остальные на другой стороне. Чтобы посчитать их, будем двигать указатель на первую вершину на одной стороне, скажем, (0, n); обозначим диаметрально противоположную вершину за x. Тогда вторая вершина может быть любой на отрезке [n + 1, s], а третья может быть любой на [s, 2n - 1]. Количество этих точек легко посчитать, используя частичные суммы на круге. Заметьте, что s может быть как второй, так и третьей вершиной одновременно (строки могут повторяться). Тогда мы двигаем этот указатель через все вершины одной стороны и обновляем ответ. Аналогично мы решаем случай, когда первая вершина на второй стороне, а обе других на противоположной.

Остаётся только быть осторожными с формулами в каждом случае.

Сложность решения: из-за сортировки.

Post Scriptum

Какими были ваши решения? Не стесняйтесь поделиться любыми решениями или мыслями! Например, было ли в DivI E решение, проще авторского?