Codeforces Round #353 (Div. 2) Editorial

Revision ru4, by komendart, 2016-05-17 16:06:11

Когда-нибудь я расположу C и D в правильном порядке :)

675A - Бесконечная последовательность

Во-первых, в случае c = 0 мы должны вывести YES если a = b, иначе вывести NO.

Если b принадлежит последовательности, то b = a + k * c, где k является неотрицательным целым числом.

Поэтому ответ YES если (b - a) / c является неотрицательным целым, иначе ответ NO.

Code

675B - Восстановление картины

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).

Code

675C - Денежные операции

У нас есть массив ai и мы должны обнулить все числа внутри него с помощью минимального количества операций. Сумма всех чисел в массиве равна нулю.

Мы можем разделить массив на части с нулевой суммой, состоящие из последовательных элементов (первый и последний элемент считаются последовательными). Если часть имеет длину l, то мы можем обнулить ее с помощью l - 1 операции.

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

Одна из частей состоит из префикса и, возможно, суффикса массива. Остальные части являются подмассивами.

Давайте посчитаем префиксные суммы. Заметим, что префиксные суммы перед частями-подмассивами равны между собой, так как сумма чисел в каждой части равна нулю.

Следовательно, ответ равен n - f, где f — количество вхождений самого частого элемента среди префиксных сумм.

Бонус: как взламывать решения с переполнением?

Code

675D - Построение дерева

У нас есть двоичное дерево поиска и мы должны уметь быстро добавлять в него числа.

Пусть сейчас мы должны добавить число 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.

Это всё. Сложность решения .

Code

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.

Code

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English komendart 2016-05-17 16:06:41 131
ru4 Russian komendart 2016-05-17 16:06:11 5100 Мелкая правка: 'ли $a = b$ иначе выв' -
ru3 Russian komendart 2016-05-16 22:18:48 48 Мелкая правка: ' + 1$ to $n - 1$ and $a_m' -> ' + 1$ to $a_i$ and $a_m'
en4 English komendart 2016-05-16 22:18:16 48 Tiny change: ' + 1$ to $n - 1$ and $a_m' -> ' + 1$ to $a_i$ and $a_m'
ru2 Russian komendart 2016-05-16 22:05:51 3329
en3 English komendart 2016-05-16 22:05:04 3289
en2 English komendart 2016-05-16 21:36:25 0 (published)
en1 English komendart 2016-05-16 21:35:55 3341 Initial revision for English translation
ru1 Russian komendart 2016-05-16 21:33:45 3341 Первая редакция (сохранено в черновиках)