382A - Ксюша и чашечные весы

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

382B - Разрушители чисел

В этой задаче нужно было понять, что из себя представляет хитрая операция Артура. На самом деле, если перед выполнением всех действий сделать присвоение b = w - b - 1 (то есть как бы перевернуть ситуацию), то операция аналогична присвоению b = (b + x) % w. Причем если происходит переполнение через w, то дополнительно происходит присвоение a = a - 1.

Таким образом, если выполнить k таких операций, то переменные изменятся так: b = (b + k·x) % w, a = a - (b + k·x) / w, c = c - k. Зная это, легко решить задачу бинарным поиском по ответу.

382C - Арифметическая прогрессия

В этой задаче нужно было разобрать несколько несложных случаев:

1) если n = 1, то ответ: -1, потому что любые два числа будут являться арифметической прогрессией;
2) если массив состоит целиком из одного числа, то ответ: эта единственная константа;
3) если вам уже дана арифметическая прогрессия, то ответ это 2 числа: minVal - d, maxVal + d, где minVal — минимум, maxVal — максимум, d — разность прогрессии.
Однако, если n = 2, то в этом случае ответ бывает 3 числа (как, например, в последнем тестовом примере, когда разность (a[1] - a[0]) четна);

4) иначе, возможно, в прогрессии пропущено ровно одно число и его можно аккуратно найти двигаясь по исходному массиву (предварительно его удобнее отcортировать). Разность прогрессии можно вычислить, как d = min(a[i + 1] - a[i]) (если n > 2);
5) во всех иных случаях ответ 0;

382D - Ксюша и пешки

В этой задаче из всех клеток кроме # один переход. Поэтому граф на клетках является почти фунцкиональным графом. Если в этом графе есть цикл, то очевидно ответ -1, потому что этот цикл имеет длину не менее 2 и мы можем разместить на нем две наши пешки.

Иначе в графе нет циклов. Найдем в нем самый длинный путь, пусть его длина len. Тогда если мы расположим две наши пешки в первую и вторую клетку пути, то ответ на задачу уже будет 2·len - 1.

Однако, иногда можно получить ответ 2·len, если в этом графе есть два непересекающихся по вершинам пути (вершины, не являющиеся #). Непересекающиеся они будут потому, что если вдруг они пересеклись в какой-то клетке, то дальше они будут совпадать (а по условию задачи такие ходы совершать нельзя).

Остается проверить есть ли в этом графе два непересекающихся по вершинам (не #) пути длины len. Это можно сделать как угодно. Например, посчитать для каждого истока v величину d[v] длины пути из него. После серией поисков в глубину из всех истоков с максимальным d[v] = len проверить найдутся для два непересекающихся пути. (если очередной поиск в глубину не находит поюзанной вершины, значит этот путь новый).

382E - Ксения и комбинаторика

Чтобы решить задачу, нужно было посчитать количество деревьев с заданными свойствами. Сделать это можно с помощью динамического программирования. Основная идея динамического программирования в том, что размер максимального паросочетания в дереве ищется простой линейной динамикой dp[v][used] (v —- вершина, used —- уже использована она в паросочетании или нет), поэтому для подсчета количества деревьев достаточно включить в состояние динамики два значения dp[v][0] и dp[v][1].

Другими словами, нужно написать динамику z[n][dp0][dp1], значение которой — это количество подвешенных деревьев, состоящих из n вершин, в корне которых динамика dp[root][0] = dp0, а dp[root][1] = dp1. Если просто написать такую динамику она будет получить TL по времени. Из этого положения можно выйти двумя способами. Либо посчитать все значения динамики прекалком, немного оптимизировав код, либо ассимптотически оптимизировать динамику.

Авторское решение использует второй подход. Для того, чтобы оптимизировать динамику достаточно заметить, что значение dp0 отличается от значения dp1 не больше чем на 1. То есть либо dp0 = dp1, либо dp0 = dp1 + 1. Тогда динамика превращается в динамику r[n][dp0][add], которая работает сильно быстрее. Другая важная оптимизация состоит в том, что возможных троек (n, dp0, add), для которых значение r[n][dp0][add] ненулевое очень мало (около 250). Это значит, что достижимых состояний динамики не много, поэтому если написать ее "лениво" с отсечениями, программа будет работать в несколько раз быстрее.

Комментарии, которые описывают решения (некоторые отличаются):

http://mirror.codeforces.com/blog/entry/10423#comment-158177
http://mirror.codeforces.com/blog/entry/10423#comment-158182