Задача A. Div2.
Заметим, что число x может встречаться в столбце i только один раз — в строке x / i. Переберем столбец i, проверим, что x делится нацело на i, а также x / i ≤ n. Если все условия выполнены, обновим ответ.
Асимптотика — O(n)
Код
Задача B. Div2.
Рассмотрим два случая: n > m и n ≤ m.
Пусть n > m, рассмотрим суммы на префиксах. По принципу Дирихле, найдутся две равные суммы по модулю m. Пусть Slmodm = Srmodm. Тогда сумма чисел на отрезке с l + 1 по r по модулю m равна нулю, то есть ответ точно "YES".
Пусть n ≤ m, то решим задачу динамикой за O(m2). Пусть can[i][r] — можем ли мы, используя первые i предметов, получить остаток r от деления на m. Переходы в динамике понятны: либо мы берем предмет и переходим в состояние can[i + 1][(r + ai) mod m], либо не берем и переходим в состояние can[i + 1][r].
Асимптотика — O(m2).
Код
Задача A. Div1.
Пусть Петя не спросил число pk, где p — простое, а k ≥ 1. Тогда, Петя не сможет отличить число pk - 1 от числа pk.
Значит, нужно спросить все числа вида pk, где p — простое, а k ≥ 1. Несложно убедиться, что это позволит угадать и все остальные числа.
Асимптотика O(N1.5) или O(NloglogN) в зависимости от теста на простоту.
Код
Задачи B. Div1.
Рассмотрим дерево-ответ. Заметим, что центры этого дерева могут перейти только в центры при применении перестановки. Это означает, что в перестановке обязательно должен быть цикл длины 1 или 2.
Пусть в перестановке есть неподвижная точка. Тогда мы можем подсоединить ребрами к этой вершине все остальные. Несложно убедиться, что это корректный ответ.
Например, пусть дана перестановка (4, 2, 1, 3). В перестановке есть неподвижная точка 2, поэтому подсоединим ко второй вершине все остальные. Получатся ребра дерева (1, 2), (2, 3), (2, 4).
Пусть в дереве-ответе есть два центра. Удалим ребро между ними, дерево разобьется на две компоненты. Несложно понять, что они должны перейти друг в друга при применении перестановки. Это означает, что все циклы перестановки должны быть четной длины.
Понятно, как построить ответ, если все циклы четной длины, и есть цикл длины два. Проведем ребро между вершинами из цикла длины два, вершины всех остальных циклов будем присоединять по очереди к центрам.
Например, рассмотрим перестановку (6, 5, 4, 3, 1, 2). В перестановке есть два цикла: (3, 4) и (1, 6, 2, 5). Соединим ребром вершины (3, 4), все вершины другого цикла присоединим по очереди к этим двум вершинам, получим ребра (1, 3), (6, 4), (2, 3), (5, 4).
Асимптотика — O(N).
Код
Задача C. Div1.
Разобьем квадрат 106 × 106 вертикальными линиями на 1000 прямоугольников 103 × 106. Пронумеруем эти прямоугольники от 1 до n в порядке слева направо. Обойдем их тоже слева направо, а внутри каждого прямоугольника обойдем точки по возрастанию y-координаты, если это четный по номеру прямоугольник, и по убыванию, если нечетный.
Посчитаем длину такого пути, будем считать независимо по каждой координате. По y-координате мы пройдем суммарно 1000 прямоугольников от 0 до 106, то есть суммарно 109, По x-координате, чтобы дойти до следующей точки внутри прямоугольника, мы потратим не более 1000 на точку, и 1000 раз пройдем не более 2000 до следующего прямоугольника, то есть суммарно 109 + 2000000.
Итого, длина пути не более 2 * 109 + 2000000, что подходит под ограничения на длину.
Асимптотика — O(n * log(n))
Код
Задача D. Div1.
Будем оптимизировать первое же решение, которое приходит в голову за O(m * dmax): посчитаем can[t][v] — можно ли добраться до вершины v, пройдя по ровно t ребрам.
Теперь заметим, что множество ребер, по которому мы можем ходить меняется только m раз. Отсортируем ребра в порядке возрастания di, т.е. для всех i di ≤ di + 1. Будем считать динамику can[t][v] только для t = di. Пусть мы хотим перейти от can[di] к can[di + 1]. Поскольку набор ребер не меняется с момента di до di + 1, мы можем возвести матрицу смежности в степень di + 1 - di и применить ее к can[di].
Пусть мы насчитали все can[di][v]. Теперь зафиксирует ребро с максимальным di, по которому мы пройдем в нашем кратчайшем пути. Мы знаем все вершины, в которых мы можем находиться в момент di, далее нужно найти кратчайший путь из них в вершину m по открытым для нас ребрам и обновить ответ. Матрицу кратчайших расстояний можно посчитать Флойдом, поэтому обновление ответа не составит труда.
Получилось решение за O(m * n3 * log(dmax)), которое, к сожалению, работает долго.
Далее нужно заметить, что матрица смежности состоит из ноликов и единичек, поэтому её можно возводить в степень битовым сжатием за O(n3 / 32). Это дает решение за O(m * n3 * log(dmax) / 32), что спокойно заходит по времени.
Код
Задача E. Div1.
Сначала решим чуть более простую задачу: пусть вне зависимости от двудольности/недвудольности запросы выполняются, а от нас требуется лишь ответить, будет ли граф двудольным/недвудольным после запроса.
Тогда мы могли бы применить решение, похожее на решение задачи Dynamic Connectivity Offline за O(nlog2n). Опишем его подробнее:
Вначале пусть ребра только добавляются. Тогда можно воспользоваться системой непересекающихся множеств, где, кроме предка, будем хранить четность пути до предка, а также флаг двудольности текущего графа. Теперь мы можем найти четность пути до корня — просто пропрыгать до предка, проксорить четности. Теперь, когда мы проводим ребро между двумя компонентами, мы можем посчитать четность путей до вершин этой ребра, а значит, и установить четность прыжка из корня одной компоненты в корень другой компоненты. Если ребро проходит внутри одной компоненты и четности пути до корня совпадают, нужно убрать флаг двудольности текущего графа.
Теперь пусть ребра иногда удаляются. Для каждого ребра и каждого цвета мы знаем отрезки запросов, когда это ребро будет в графе заданного цвета. Давайте построим дерево отрезков на запросах, в каждой вершине будем хранить список ребер, которые будут включены на этом подотрезке. Каждый отрезок дерево отрезков разобьет на log кусочков, поэтому в сумме количество добавлений ребер на кусочке будет порядка n * log.
Теперь, можно обойти это дерево отрезков в глубину с системой непересекающихся множеств с откатами. Мы входим в вершины, применяем все запросы добавления ребра в данной вершине, обходим потомков, а затем откатываем снм до состояния, в котором оно было на входе в эту вершину. Когда мы находимся в листе, отвечаем на соответствующий запрос.
Вернемся к нашей задаче. Вышеописанную технику в явном виде мы применить не можем, потому что не знаем точно, на каких отрезках запросов ребра будут существовать.
Зато мы можем сделать следующее. Изначально применим операцию до первого момента появления ребра в запросах. Теперь, когда мы находимся в листе, мы узнали, какого цвета это ребро будет до следующего его появления в запросах. Поэтому, давайте сделаем обновление на отрезке со следующего запроса до следующего появления этого ребра. Для каждого листа мы сделаем не более одного обновления, поэтому суммарное время работы O(nlog2n).
Асимптотика — O(nlog2n).
Код
Если что-то неясно, непонятно или невнятно написано, задавайте любые вопросы.
