DivII A. Печеньки

Самый лёгкий способ решить задачу — сперва посчитать всю сумму чисел, и затем посчитать количество чётных разностей между этой суммой и каждым числом. Однако маленькое наблюдение позволит написать решение немного эффективней: помимо суммы (sum) посчитаем также, сколько среди данных чисел есть чётных (even) и нечётных (odd). Тогда, если сумма нечётна, то ответ — odd, иначе — even. Время O(n), память O(1).

DivII B. Шнурки и шестиклассники

Маленькие ограничения позволяют нам написать решение «в лоб». Будем хранить данный граф в матрице смежности, и симулировать происходящее. Также будем хранить степень каждой вершины отдельно, чтобы быстро находить детей, которые связаны только одним шнурком. Тогда при каждой итерации удаляем все вершины со степенью 1 и все грани, которые соединяются с этими вершинами; продолжаем до тех пор, пока не останется таких вершин. Ответом будет количество произведённых итераций. Время O(n³), память O(n²).

DivII C / DivI A. Статуи

Произведём симуляцию падения статуй. При каждой итерации будем сдвигать все статуи на одну клетку вниз. Перед каждым ходом (итерацией) будем получать список всех полей, куда Маша может пойти (до того, как статуи передвинутся на одну клетку вниз), используя список тех полей, куда она могла придти с прошлого хода (единственное, из полей с прошлого хода можно использовать только те, в которые после конца прошлого хода не переместилась статуя). Логично, что через 8 любых ходов на доске не останется ни одной статуи. Поэтому, если список  доступных Маше полей после 8-ого хода не пуст, то она может добраться до Ани, потому что дальше её ходы ничто не ограничивает. Время O(9· 8³) = O(1), память O(8²) = O(1).

DivII D / DivI B. Строка

Вначале ликвидируем случай невозможности — такой строки нет, если k больше, чем количество подстрок, т.е. , где n — длина строки.

Теперь заметим, что для каждой буквы мы можем быстро оценить, сколько подстрок начинаются именно с этой буквы. Действительно, если буква стоит на позиции i (нумеруя с 1), то количеством подстрок, начинающихся с позиции i, является n - i + 1. Тогда количество строк, которые начинаются с конкретной буквы, будет сумма всех таких значений для позиций, в которых стоит эта буква.

Далее, используя найденную информацию, не сложно выяснить, с какой буквы будет начинаться нужная подстрока (потому что в слове при лексикографическом сравнении буквы слева важнее, чем буквы справа). Теперь заметим, что тоже самое рассуждение мы можем применить и для следующей буквы нужного слова, только теперь нужно проверить только такие буквы, которые следуют после первой буквы слова. Таким образом, мы повторяем итерации и для 3-ей, 4-ой, ... букв до тех пор, пока не найдём нужную строку. Чтобы не искать каждый раз нужные позиции, будем хранить их отдельно; при каждой итерации сдвигать их на одну позицию направо и исполнять алгоритм только для них, а после нахождения i-того символа убирать те позиции, буквы в которых не равны с найденным символом. Время благодаря k ≤ 10⁵ не квадратичное (самому ещё не получилось доказать), память O(n).

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

DivII E / DivI C. Игра с прямоугольниками

Рассмотрим все левые и правые границы всех k внутренних прямоугольников, вместе их 2k. Присвоим им произвольные 2k координат между левой и правой стороной данного прямоугольника, это можно сделать способами. То же самое сделаем и с верхними и нижними границами, это можно сделать способами. Заметим, что каждая пара таких размещений однозначно определяет одно искомое расположение, и все такие расположения можно определить одной парой размещений. Поэтому ответом является . Так как n и m не больше 1000, то коэффициенты можно посчитать с помощью треугольника Паскаля (не забывая вычислять по данному модулю). Время O(max(n, m)²), память O(max(n, m)²).

DivI D. Числа

У меня эта задача ассоциировалась с атомами и молекулами. :) Представим, что каждое из чисел имеет две связи, где связь соединяется с другой по заданным правилам. Тогда решение существует тогда и только тогда, когда все связи соединены, и из каждого элемента по связям можно дойти до любого другого элемента; также решения не существует, если присутствуют числа x, x + 2, но x + 1 не присутствует.

Пусть у нас есть числа a, a + 1, ..., b, тогда количество связей у них 2|a|, 2|a + 1|, ..., 2|b|, где |x| — количество чисел x. Ясно, что 2|a| связей от 2|a + 1| «съедают» элементы a. У a + 1 свободными остаются p = 2|a + 1| - 2|a| связей. Аналогично, эти p связей соединяются с a + 2 элементами и т.д. В конце концов, если у b - 1 свободными остаются q связей, то должно быть q = 2|b|, чтобы завершить цепочку. Остаётся только проверить все эти соотношения (учитывая то, что цепочку нельзя завершить раньше, чем не истрачены все связи — то есть, вычисляемый p не может быть 0). Время (т.к. данные числа нужно отсортировать), память O(n). Для простоты вычислений можно ещё заметить, что 2|a| можно заменить на |a|, из-за этого ничего не изменится.

DivI E. День рождения

См. хороший разбор здесь.