В этой задаче нужно посчитать количество различных чисел из входных данных cnt и вывести 4–cnt. Это можно было сделать как угодно. Например, сложить все числа в сет и посчитать его размер.
В этой задаче нужно было аккуратно перебрать всевозможные сдвиги - N < = x, y < = N, посчитать текущий ответ и найти максимум среди всех полученных. Асимптотика решения O(N4).
Задача решалась при помощи динамического программирования. Посчитаем динамику z[x][y][st][mask] ---является ли квадрат с верхним левым углом в клетке (x, y) фракталом уровня вложенности st, который получен исходным квадратом с цветами, обозначаемыми mask. Значение z[x][y][st][mask] хранит 0 или 1. Состояний в такой динамике O(N2·Log(N)·24). Переходы в ней достаточно очевидны. Если st = 1, это означает, что нужно честно проверить квадрат размера 2*2 с верхним левым углом в клетке (x, y) на совпадение с исходной маской mask. Если st > 1, нужно разделить этот квадрат на четыре меньшие части и проверить, что для них всё выполняется. Если значение mask в одной четверти означает черный цвет, нужно проверить, что вся четверть является черной. Это можно сделать за O(1) при помощи частичных сумм на прямоугольниках. Если же четверть имеет белый цвет, нужно проверить, что она является фракталом уровня вложенности st–1 с той же маской mask. Получается не более 4 переходов из каждого состояния.
Чтобы посчитать ответ на задачу, нужно перебрать всевозможные левые верхние углы квадратов, всевозможные маски и для каждого уровня вложенности проверить, что данный квадрат нам подходит. Это и делает наша динамика.
В этой задаче нужно было воспользоваться тем, что последовательность s имеет циклический вид из-за своей структуры. Также было важно, что 2 < = z < = 6. Для каждого z выпишем последовательность s и увидим, что длина её периода 2 * (z–1).
Тогда, для каждого z и каждого модуля 0 < = mod < 2 * (z–1) заведем отдельное дерево отрезков или фенвика, которое нам поможет отвечать на запросы. Нужно быть аккуратным с памятью, нам требуется O(Z·(2·Z)·N) памяти. Если запрос на изменение в позиции, нужно обновить z значений в деревьях с соответствующими модулями для этой позиции. Если запрос на сумму, нужно посмотреть все 2·(z–1) модулей и для каждого отдельного посчитать сумму, домножив её на нужный коэффициент, который мы берем из последовательности s. Решение имеет сложность O(Z·N·Log(N)).
228E - Как два пальца об асфальт
У этой задачи оказалось много решений. Первоначально предполагалось решение, которое решало систему равенств по модулю 2, используя алгоритм Гаусса. Расскажем другое простое решение.
Вершины, которые мы возьмем в ответ, назовем включенными. Во-первых, очевидно, что каждую вершину мы включим не более одного раза. Теперь посмотрим на произвольное ребро (x, y) цвета c. Нам нужно, чтобы его цвет в результате равнялся 1. Если c = 1, нужно либо не включать вершины x и y, либо нужно их обе включить. Если c = 0, нужно включить либо x, либо y. Таким образом, если мы рассмотрим произвольную вершину v и переберем, включим ее или нет, то можно однозначно восстановить, какие вершины придется включить в компоненте связности вершины v. Если в некоторый момент у нас возникнет коллизия, мы выбрали неправильный цвет у вершины v. Если хотя бы одну компоненту покрасить не удастся, нужно вывести Impossible. Это можно реализовать за O(N + M) серией поисков в ширину.
По последней задаче: если с=0, то нам нужно включить либо х, либо у. Разве не так?
да, наоборот, исправил
Собственно говоря, решение задачи Е и есть решение системы по модулю 2, каждое уравнение которой связывает две переменные. Отсюда, в частности, следует, что одну вершину каждой компоненты связности мы можем красить произвольно, поскольку значение не меняется, если перекрасить все вершины в компоненте (в каждом уравнении +1 сокращается).
"Во-первых, очевидно, что каждую вершину мы включим не более одного раза" А почему в первом тесте 3 в начале и в конце? Или это не вершины взятые в ответ?
"В случае, если решений несколько выведите любое."
Здесь имеется ввиду оптимальное решение, в нем нет повторяющихся вершин. А в тесте просто для отвода глаз дано крайне неэффективное решение.
А как доказать, что каждая вершина в оптимальном ответе будет встречаться не более 1 раза?
Очевидно, ремонт дорог в одном городе — замена всех 0 на 1, а 1 на 0. Если выполнить ее 2 * n раз, то это то же самое, что не выполнять, а если выполнить 2 * n + 1 раз, это то же, что выполнить 1 раз.
Да, это так и это очевидно: если город, примыкающий к дороге ремонтировать четное число раз — состояние данной дороги не изменится. Однако кто мешает разное число раз включить два города, примыкающих к этой дороге?
Как решить 2-sat om задачу Е? Я добавляю рёбра !a-b и !b-a для st=0, или (a-b b-a !a-!b !b-!a) для st=1, и далее 2-sat, не получается.
Цитата из разбора задачи C: "Если значение mask в одной четверти означает черный цвет, нужно проверить, что вся четверть является черной. Это можно сделать за O(1) при помощи частичных сумм на прямоугольниках."
Кажется, достаточно проверить, что
z[x'][y'][st - 1][15] == 1(если единичный бит в маске означает, что четверть черная)Why no pattern could be like this one? (228C - Fractal Detector)