Adiv2. Рассмотрим массив A целых чисел от 1 до nk. Удалим из него все числа a_i, а все, что осталось, запишем в массив B. Массив B будет состоять из (n - 1)k элементов. Теперь для i-го ребенка следует вывести числа a_i, B[(n - 1) * (i - 1) + 1], B[(n - 1) * (i - 1) + 2], ... B[(n - 1) * (i - 1) + n - 1] (индексация B начинается с 1).

Автор — Gerald .

Bvid2. Решение 1. Напишем перебор по всем числам, состоящим из не более чем 9 цифр (число 10⁹ преверим отдельно). Схематично это будет выглядеть так:

dfs( int num ) // запускать как dfs(0)
  if (num > 0 && num <= n) ans++
  if (num >= 10^8) return
  for a = 0..9 do
    if num*10+a>0 then
      if число num*10+a содержит не более 3х цифр then
        dfs( num*10+a )

В ans теперь будет находиться ответ. Напишем, запустим — увидим, что работает быстро (это решение выполняется одинаковое время на всех тестах). Отошлем.

Решение 2. Будем строить все безусловно счастливые числа с помощью битовых масок. А именно: переборем длину числа L, пару цифр x и y, а так же битовую маску m длины L. Если i-ый бит m равен 1, то в i-ый разряд поставим x, иначе y. Итого будет сгенерировано порядка 10³ × 2¹⁰ чисел (это очень грубая оценка, можно показать, что их будет раз в 10 меньше).

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

Автор — Gerald

Adiv1, Cdiv2 Давайте посмотрим как будет меняться функция f на всех суффиксах последовательности a. Значения f будут расти с увеличением длины суффикса, причем при каждом увеличении все единичные биты так и останутся единицами, а некоторые нули перейдут в единицы. Таким образом, произойдет не более k увеличений, где k — число бит (в данном случае k = 20). То есть среди всех суффиксов будет не более k + 1 различных значений f.

Теперь мы можем просто идти по массиву a слева направо и поддерживать в массиве m (или в сете) значения f для всех подотрезков, заканчивающихся в текущей позиции (его размер никогда не будет превышать k + 1). При переходе из позиции i - 1 в позицию i мы заменяем m = {m₁, m₂, ..., m_t} на {a_i, m₁|a_i, m₂|a_i, ... m_t|a_i}, после чего удаляем повторяющиеся значения (в случае сета сет все делает за нас). После этого новые значения отмечаем в глобальном массиве флагов (или запихиваем в глобальный сет). В конце выводим количество найденных значений.

Авторы — Gerald , Ripatti

Bdiv1, Ddiv2 Для каждого ребра будем проверять может ли оно быть телом гидры. Зафиксируем какое нибудь ребро (u, v) (порядок вершин в ребре имеет значение, т.е. потом еще нужно будет проверить ребро v, u). Теперь нам нужно выбрать подмножество из h вершин, соединенных с u, и подмножество из t вершин, соединенных с v (u и v в них, конечно, не должны входить). Сложность заключается в том, что эти 2 множества не должны иметь общих вершин.

Если или , то тут гидры, очевидно, нет.

Иначе, если или , то тут гидра всегда найдется — даже если все соседние к u и v вершины общие, их количества хватит, чтобы все нужным образом поделилось.

Иначе, остается случай и . Тут можно найти общие соседние вершины за время O(h + t), работая с массивом флагов. Когда общее подмножкство вершин найдено, проверить наличие гидры несложно. Поскольку h и t маленькие — проверка будет работать быстро.

UPD Как найти общие вершины за O(h + t) при помощи массива флагов? Просто в самом начале заведем булевый массив длины n. Затем при каждой проверке будет сделать следующее. За отметим в массиве всех соседей u. После этого посмотрим всех соседей v за и те вершины, для которых в массиве флагов стоит true, будут являться общими. Когда множество общих вершин найдено, почистим массив флагов за : просто еще раз пройдемся по соседям вершины u. Поскольку и , получим итоговую оценку O(h + t).

Итого за время O(m(h + t)) будет найдено ребро, которое должно быть телом гидры, или будет установлено, что гидры в графе нет. За дополнительное время O(m) можно построить саму гидру.

В этой задаче есть решение за , которое не зависит от h и t, однако это решение сложнее.

Автор — Ripatti

Cdiv1, Ediv2 Сначала промоделируем все перемещения дяди Вани "вхолостую". Пусть он побывал в точках (x₀ + 1 / 2, y₀ + 1 / 2), (x₁ + 1 / 2, y₁ + 1 / 2), ... , (x_n + 1 / 2, y_n + 1 / 2). Интересными для нас координатами по оси x будут x₀, x₀ + 1, x₁, x₁ + 1, ... x_n, x_n + 1, по оси y — y₀, y₀ + 1, y₁, y₁ + 1, ... y_n, y_n + 1. Добавим к этим координатам границы поля.

Построим "сжатое" поле: каждая клетка этого поля обозначает прямоугольник изначального поля, находящийся между двумя соседними интересными координатами. Размер этого сжатого поля будет порядка O(n) × O(n). Пусть изначально все клетки поля белого цвета. На этом сжатом поле промоделируем все перемещения еще раз и покрасим черным цветом все обработанные ядом клетки. Каждое перемещения затронет O(n) клеток, поэтому все перемещения смоделируются за O(n²).

Теперь промоделируем действия жуков. Запустим поиск в глубину (или поиск в ширину) и зальем красным цветом все клетки, которые будут съедены жуком.

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

Итого решение за O(n²).

Автор — Ripatti

Ddiv1 Нам нужно для каждого столбика кубиков узнать высоту самого нижнего кубика, который мы сможем увидеть — все кубики выше него мы тоже увидим.

Посмотрим на город из кубиков сверху — увидим сетку размера n × n. Проведем через каждый узел сетки прямую, параллельную вектору v. Нам интересно только что происходит в каждой из полос между этими прямыми. Каждый столбик покрывает некоторый отрезок из полос длины порядка O(n).

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

Теперь отсортируем все столбики по расстоянию от наблюдателя и в этом порядке будем выполнять запросы двух видов:

1. Минимум на отрезке. Нужен нам для того, чтобы определить высоту самого нижнего видимого кубика.

2. Замена значений на max(a_i, h) на отрезке. Это нужно для "рисования" стоблика.

По сути это все решение, дальше только возникает вопрос о структуре данных, которая позволяет быстро выполнять запросы. Возможны варианты: декомпозиция на блоки (длина каждого блока должна быть порядка , поскольку длины запросов длины O(n); это дает решение за O(n^5 / 2)), дерево отрезков (сложность ), тупо массив (заходит если все оптимизировать по кэшу, O(n³)).

Автор — Ripatti

Ediv1 Будем конструктивно строить матрицу. На каждом шаге у нас будет массив групп столбцов. Порядок групп определен, однако порядок столбцов внутри группы — нет.

Строки можно менять местами как нам угодно, поскольку это не влияет на ответ.

Опишем процесс построения матрицы. Сначала найдем строку, в которой больше всего единиц. Поменяем ее местами с первой строкой. После этого создадим две группы. В первую поместим все столбцы, где в первой строке стоит 1, во вторую — где стоит 0. Группа, где собрались 0 — "особенная" (об этом ниже).

Далее будем несколько раз делать следующее: искать строку, для которой хотя бы в 2х группах имеется хотя бы по 1 единице. Для каждой такой строки мы можем однозначно определить положение единиц в ней. Либо определить, что расположить нужным образом единицы в ней нельзя и сразу вывести NO. После того, как положение единиц определено, некоторое группы разделяются на 2 подгруппы.

Следует отметить особенность "особенной" группы — из нее мы можем перекидывать столбцы в самое начало матрицы. Ситуации когда будет непонятно какие столбцы перекидывать, а какие нет не возникнет, поскольку в самом начале мы выбирали строчку с наибольшим числом единиц.

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

Решение работает за O(n³). Его можно улучшить до , но этого не требовалось.

UPD Существут решение за O(n²), основанное на PQ-деревьях, как сообщил mugurelionut. Подробнее тут.

Автор — Ripatti