483A - Опровержение гипотез

Автор задачи gridnevvvit

В задаче предполагалось два решения:

1. Перебрать всевозможные тройки, и проверить, правда ли, что для этой тройки гипотеза неверна. Асимптотика такого решения O(n³logA)
2. Разобрать несколько случаев. Например, это можно сделать так:

  if (l % 2 != 0)
      l++;
   
  if (l + 2 > r)
    out.println(-1);
  else
    out.println(l + " " + (l + 1) + " " + (l + 2));
 

Авторское решение: 8394832

483B - Друзья и подарки

Автор задачи gridnevvvit

Авторское решение — бинпоиск по ответу. Во-первых, заметим, что если из набора 1, 2, ..., v можно собрать подарки, то и из набора 1, 2, ..., v, v + 1 можно собрать подарки. Пусть f(v) — функция, возвращающая ответ на вопрос: правда ли, что из набора 1, 2, ..., v можно собрать подарки друзьям. пусть f₁ — количество чисел, которые делятся на x, а f₂ — количество чисел, которые делятся на y. и число both — количество чисел которые делятся и на x, и на y. Тогда в первую очередь первому другу мы постараемся отдать f₂ - both чисел, а второму — f₁ - both чисел. После этого нужно проверить, сможем ли мы раздать числа, которые не делятся ни на одно из чисел x и y.
Таким образом, решение за

Авторское решение: 8394846

483C - Разнообразная перестановка / 482A - Разнообразная перестановка

Автор задачи gridnevvvit

Разберем, как работает решение на большом примере, например

1 10 2 9 3 8 4 7 5 6

На нечетных местах мы имеем возрастающую последовательность 1, 2, 3 .., а на четных — убывающую последовательность n, n - 1, n - 2, ... Получим таким образом решение, выведем первые k чисел указанной выше последовательности, а потом сделаем так, чтобы соседние разности были равны единице.

Решение за асимптотику O(n).

Авторское решение: 8394876

483D - Интересный массив / 482B - Интересный массив

Автор задачи gridnevvvit

Будем решать задачу отдельно для каждого бита. Предположим, что пришло новое ограничение: l[i], r[i], q[i]. Если в числе q[i] бит с номером pos единичный, то у всех чисел на отрезке [l[i], r[i]] этот бит тоже будет единичным. Теперь можно воспользоваться стандартной идеей прибавления на отрезке оффлайн. Сделаем два прибавления в массиве s[bit] — в позиции l[i] мы сделаем прибавление 1, а еще одно в позиции r[i] + 1, там мы прибавим -1. Таким образом, если мы насчитаем частичные суммы на массиве s[bit], то, если s[bit][i] > 0, то бит bit в этом числе будет единичным, иначе — нет. После этого можно реализовать дерево отрезков, чтобы проверить выполнимость изначальных запросов.

Авторское решение: 8394894

483E - Игра со строками / 482C - Игра со строками

Автор задачи gridnevvvit

Переберем все пары строк, и подсчитаем маску mask — единичные биты будут находится только в позициях, в которых эти две пары строк имеют одинаковые символы. Таким образом, используя биты, соответствующие любой подмаске маски mask, мы не сможем отличить эту пару строк, поэтому добавим в маску d[mask] биты в позиции i и j. Таким образом, в d[mask] мы храним маску тех строк, которые мы не сможем отличить по заданной маске mask. Используя указанную выше информацию, мы сможем просто насчитать эту динамику.

Теперь, когда у нас имеется эта динамика, нетрудно восстановить ответ. Переберем маску mask. Попробуем задать еще один вопрос, то есть добавить в эту маску еще один бит. После этого мы могли отгадать некоторые строки, а именно те, что останутся в виде единичных битов в маске s = d[mask] ^ d[mask | (1 << pos)] (pos — позиция нового вопроса). Осталось аккуратно подсчитать количество бит в маске s и пересчитать искомое математическое ожидание.

Авторское решение: 8394918

482D - Случайная функция и дерево

Автор задачи RoKi

Посчитаем динамику d[v][p] — ответ на задачу для поддерева вершины v с размером, имеющим четность p.

Научимся считать эту динамику для вершины v. Для начала посчитаем количество различных раскрасок при обходе потомков в порядке возрастания номеров. Умножим эту величину на 2 и получим раскраски при обходе потомков в порядке убывания номеров. Но теперь, возможно, появились раскраски, которые мы учли 2 раза. Давайте рассмотрим некоторое поддерево вершины v и поймем, когда оно учтется 2 раза.

Рассмотрим четности поддеревьев потомков, которых посетила наша функция (0 или 1). Первое, что нужно заметить: если среди этих величин есть различные значения, то такое поддерево при разных обходах будет раскрашено по-разному (это вы можете доказать сами). Теперь все наши посещенные потомки имеют одинаковые по четности размеры поддеревьев. Если размеры поддеревьев четные, то очевидно, что такое дерево учтется 2 раза. А вот если размеры поддеревьев нечетные, то нас интересуют только случаи, когда мы посетили нечетное количество потомков. Таким образом, из нашей динамики нужно вычесть количество способов раскрасить любое количество потомков с четным размером поддерева и нечетное количество потомков с нечетным размером поддерева.

Авторское решение: 8394936

482E - ELCA

Автор задачи danilka.pro

Будем обрабатывать M запросов блоками по штук (таких блоков, очевидно, тоже ). Каждый блок обрабатывается следующим образом:

Сначала поиском в глубину посчитаем для каждой вершины v значение , где u — любой предок v, а size_i — размер поддерева вершины i, включая саму вершину. Эта величина характеризует изменение ответа при 'отрывании' или 'прикреплении' вершины v, а именно, после выполнения одной из этих операций ответ изменится на path_v·size_v (уменьшится или увеличится соответственно).

Тем же образом посчитаем значение ch_v — количество всевозможных пар вершин, наименьший общий предок которых равен v. Эта величина характеризует изменение ответа при изменении V_v, а именно, при изменении величины V_v на dV_v ответ изменится на ch_v·dV_v.

Выделим вершины, номера которых хотя бы один раз встречаются в нашем блоке (в худшем случае таких вершин ). Теперь запустим поиск в глубину, который отметит вершины, являющиеся наименьшими общими предками каких-либо двух выделенных вершин. С помощью метода математической индукции нетрудно доказать, что в худшем случае таких вершин будет ровно . Таким образом мы получили 'сжатое' дерево, содержащее только необходимые вершины. Предка вершины i сжатого дерева обозначим за P_i.

На следующем рисунке представлен пример такого 'сжатия'. Красным обозначены вершины в блоке запроса, синим — помеченные вершины, пунктиром — ребра P_v → v сжатого дерева.

На таком сжатом дереве нужно посчитать для каждой вершины v еще одну величину C_v — размер поддерева вершины исходного дерева, которая лежит на пути от P_v до v в исходном дереве после P_v (непосредственный сын P_v).

Попробуем обработать запрос на смену родителя вершины v с p_v на u в сжатом дереве. Ответ, как уже было сказано выше, сначала уменьшится на path_v·size_v. Теперь для каждой вершины i, лежащей на пути от корня до P_v, изменятся две величины: size_i уменьшится на size_v, а ch_i уменьшится на величину, равную size_v·(size_i - C_t), (P_t = i), а path_i останется прежним. Для всех остальных вершин j, напротив, изменится лишь величина path_j — она уменьшится на . Теперь мы получили сжатое дерево, в котором все величины посчитаны с учетом того, что поддерево вершины v было удалено. Аналогичным образом происходит пересчет величин с учетом добавления вершины v в качестве сына вершины u (не забываем обновлять также и C_v).

Посмотрим, как будет выглядеть обработка запроса на смену значения V_v вершины v. Ответ, как было описано, изменится на ch_v·dV_v. Также изменятся все path_i для вершин, лежащих в поддереве v (их несложно пересчитать с помощью значений C_to, все остальные значения останутся прежними.

Таким образом, сложность решения составляет , что в случае N = M составляет .

Авторское решение: 8394944