Когда-нибудь я расположу C и D в правильном порядке :)
675A - Бесконечная последовательность
Во-первых, в случае c = 0 мы должны вывести YES если a = b, иначе вывести NO.
Если b принадлежит последовательности, то b = a + k * c, где k является неотрицательным целым числом.
Поэтому ответ YES если (b - a) / c является неотрицательным целым, иначе ответ NO.
x a y
b m c
z d w
Число в центре может быть любым от 1 до n, потому что оно лежит внутри всех квадратов 2 × 2. Поэтому мы можем найти ответ с фиксированным числом в центре и потом домножить его на n.
Переберем все возможные x. Суммы в каждом квадрате 2 × 2 одинаковы, поэтому x + b + a + m = y + c + a + m и y = x + b - c.
Аналогично, z = x + a - d и w = a + y - d = z + b - c.
Квадрат с данными числам легален, если 1 ≤ y, z, w ≤ n. Мы должны просто проверить это.
Это было решение за O(n). Существует также решение за O(1).
У нас есть массив ai и мы должны обнулить все числа внутри него с помощью минимального количества операций. Сумма всех чисел в массиве равна нулю.
Мы можем разделить массив на части с нулевой суммой, состоящие из последовательных элементов (первый и последний элемент считаются последовательными). Если часть имеет длину l, то мы можем обнулить ее с помощью l - 1 операции.
Следовательно, если мы сложим количество операций, то получим, что ответ равен n - k, где k — количество частей. Для того, чтобы ответ был минимальным, мы должны максимизировать k.
Одна из частей состоит из префикса и, возможно, суффикса массива. Остальные части являются подмассивами.
Давайте посчитаем префиксные суммы. Заметим, что префиксные суммы перед частями-подмассивами равны между собой, так как сумма чисел в каждой части равна нулю.
Следовательно, ответ равен n - f, где f — количество вхождений самого частого элемента среди префиксных сумм.
Бонус: как взламывать решения с переполнением?
У нас есть двоичное дерево поиска и мы должны уметь быстро добавлять в него числа.
Пусть сейчас мы должны добавить число x. Найдем ранее добавленные числа l < x < r такие, что l максимально возможное, а r минимально возможное. Если только одно из этих чисел существует, то рассуждения почти не меняются. Мы можем найти l и r, например, с помощью std::set и upper_bound, если вы пишете на C++.
Мы должны сохранять отсортированный обход дерева, так как это свойство двоичного дерева поиска. Поэтому x должно быть правым потомком вершины l или левым потомком вершины r.
Пусть l не имеет правого потомка и r не имеет левого потомка. Тогда наименьший общий предок l и r (lca) не совпадает с l и r. Но тогда lca находится между l и r, а это невозможно, так как l максимально, а r минимально. Получается противоречие, поэтому l имеет правого потомка или r имеет левого потомка. Следовательно, мы точно знаем, кто из них станет предком x.
Это всё. Сложность решения .
675E - Электрички и статистика
Введем индексацию с нуля. Уменьшим каждый ai на единицу. Также сделаем an - 1 равным n - 1.
Пусть dpi — сумма кратчайших путей из i в i + 1... n - 1.
dpn - 1 = 0
dpi = dpm - (ai - m) + n - i - 1, где m лежит между i + 1 и ai и am максимально. Мы можем найти m с помощью дерева отрезков / дерева Фенвика / разреженной таблицы.
Ответ равен сумме всех dpi.