A Div 2

Если a_j делится на a_i, то тогда a_i ≤ a_j. Тогда число, на которое будут делиться все остальные числа будет не более чем любое выбранное число. То есть единственный возможный кандидат — это минимум в массиве. Поэтому просто проверим, что все элементы массива делятся на минимальный элемент.

B Div 2

Легко видеть, что Ксюша не сможет закончить ее путешествие, если существует последовательность подряд идущих # длиное более чем k.

C Div 2 / A Div 1

Первое наблюдение: мы не будем волноваться о том, как выглядят строки на самом деле, вся информация, которая нам нужна — это количество пар-символов вида: {0, 0}, {0, 1}, {1, 0}, {1, 1}. Посчитаем эти количества и будем следовать следующему жадному алгоритму:

Для первого игрока: будем брать сначала {1, 1}, если их нет, то {1,0}. Если их нет, то {0, 1} и, в последнюю очередь, будем брать {0, 0}.

Для второго игрока похожая стратегия: сначала {1, 1}, потом {0, 1}, потом {1, 0} и, в последнюю очередь, {0, 0}.

После этого сравним у кого получилось больше единичек.

D Div 2 / B Div 1

Любой путь из верхней левой клетки в правую нижнюю состоит ровно из n + m - 1 клеток. И все они должны быть покрашены в разные цвета. Значит n + m - 1 ≤ k. Исходя из маленьких ограничений на k можно предположить, что брут-форс будет работать. Единственная оптимизация для получения действительно правильного решения — это некоторая канонизация раскрасок. Будем идти по всем клеткам в некотором порядке и красить их согласно следующим условиям. Если i > j, тогда цвет i встречается позже цвета j. После такого перебора мы получим примерно миллион различных шаблонов для максимального теста.

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

E Div 2 / C Div 1

После прочтения условия, можно понять, что все, что нам нужно — это посчитать количество решений уравнения (a + b + c)³ - a³ - b³ - c³ = n в положительных целых числах.

Ключевое наблюдение это: 3(a + b)(a + c)(b + c) = (a + b + c)³ - a³ - b³ - c³, после чего мы можем просто вычислять все делители числа и идти по всем делителям x = a + b, таким что ? далее будем идти по делителям y = (a + c) ≥ x, где и в конце будем вычислять z = (b + c), такое что .

После этого, решим систему a + b = x, a + c = y, b + c = z и добавим количество подходящих решений к ответу.

D Div 1

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

Для каждого x определим y_left, y_right таким образом, что все точки (x, y), где y_left ≤ y ≤ y_right лежат внутри многоугольника и отрезок [y_left, y_right] максимально возможный.

Теперь будем считать, что мы имеем a₁, a₂, ..., a_k различных точек для каждого фиксированного x (a₁ соответствует x =  - 10⁶, a₂ соответствует x =  - 10⁶ + 1 и так далее).

Теперь требуемый ответ это a₂a₁ + a₃(a₂ + 2²a₁) + a₄(a₃ + 2²a₂ + 3²a₁) + ...

Можно заметить, что

(a₂ + 2²a₁) - a₁ = a₂ + 3a₁,

(a₃ + 2²a₂ + 3²a₁) - (a₂ + 2²a₁) = a₃ + 3a₂ + 5a₁,

и так далее.

Поэтому достаточно предпросчитать частичные суммы вида a₂ + 3a₁, a₃ + 3a₂ + 5a₁, a₄ + 3a₃ + 5a₂ + 7a₁ (разность между двумя соседними суммами составляет 2(a_i + ... + a₁), поэтому мы можем делать это за O(k)).

После предпросчета достаточно сложить полученные результаты.

E Div 1

Будем считать что у нас есть структура данных, которая позволяет осуществлять следующие операции:

• добавить точку (x, y) в структуру;

• сдвинуть все точки структуры на вектор (dx, dy);

• узнать как много точек (x,y), удовлетворяющих x ≤ x_bound, y ≤ y_bound;

• получить все элементы, которые на данный момент находятся в структуре;

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

ОБъясним, как нужно обновлять структуры. Мы будем обрабатывать все вершины в порядке обхода в глубине, и если мы находимся в листе, то мы будем создавать структуру с единственным элементом (0, 0).

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

После этого будем идти по всем сыновьям вершины и делать следующее:

• Сдвинем структуру на (1, вес ребра);

• Возьмем все элементы структуры;

• Для каждого элемента (x, y) ответим на запрос x_bound = L - x, y_bound = W - y (используем родительскую структуру);

• Добавим элементы по одному в структуру;

После этого ответим на запрос x_bound = L, y_bound = W и добавим элемент (0, 0).

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

Осталось только объяснить, как создать нужную нам структуру данных.

Существует несколько способов сделать это, один из них:

• Будем иметь маленькие подструктуры у которых размеры являются степенями двойки;

• Каждая структура — это двумерное дерево отрезков;

• Мы можем добавлять элемент следующим образом: если нет подструктуры размера 1, тогда создадим ее, иначе же возьмем все структуры размерами 1, 2, 4, ..., 2^k и перестроим в структуру размера 2^k + 1.

• Сдвиг: достаточно помнить вектор сдвига для каждой подструктуры;

• Ответ на запрос: идем по подструктурам и суммируем результаты.

Разбор задач был подготовлен sdya и Seyaua