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

D: Пусть k=1. Посчитаем для строки s динамику dp[i][mask] — количество упорядоченных наборов из n чисел из i бит каждое, где j-ый бит mask (j=0..n-1) равен 1, если j-ое число строго больше (j+1)-го, и равен 0, если эти числа равны (числа нумеруем от 1 до n, нулевое число это само s). В начале dp[0][0] = 1, в конце ответ хранится в dp[|s|][2^n-1] (все числа различны и максимальное из них строго меньше s), переходы делаются перебором набора i-ых битов.

Заметим, что точно такую же динамику можно считать, беря начальным значением dp[0][mask] = 1 для любой маски mask, давайте за a[mask1][mask2] обозначим dp[|s|][mask2], когда за начальное значение взято dp[0][mask1] = 1.

Теперь заметим, что для k=2 можно просто перебрать "маску равенств" после первых |s| бит, т.е. ответ для k=2 это сумма a[0][z] * a[z][2^n — 1] по всем маскам z. Заметим, что если считать, что a — матрица, то ответ для k=2 — это элемент с тем же самым индексом, что при k=1, но не матрицы a, а матрицы a^2. Точно так же ответ для произвольного k хранится в том же самом месте в матрице a^k. Осталось воспользоваться бинарным возведением матрицы в степень.

Ещё одно решение D за другую сложность. Забудем, что числа должны быть различными. Тогда ответ можно насчитать такой динамикой: dp_ij — ответ для i-ого префикса, если j чисел из набора уже меньше, чем R, а остальные равны R. С помощью той же идеи, что описал Copymaster, можно посчитать её за O(n³ * (|s| + log(k)). Теперь нужно посчитать все множества, в которых есть различные числа. Для этого перебираем все разбиения на подмножества, для каждого разбиения считаем, сколько подмножеств чётного размера, а сколько — нечётного. Пусть чётных множеств x, а нечётных множеств — y. Тогда количество способов выбрать n чисел, так чтобы все числа в одном множестве были равны, а в разных — различны, равно ans_x * (r - x) * (r - x - 1) * ... * (r - x - y + 1), где ans_x — количество множеств размера x без одинаковых элементов. Итоговая сложность — O(n⁴ * (|s| + log(k)) + n² * B_n), где B_n — n-ое число Белла.

Хватило промоделировать последние 8к шагов влоб

Рассмотрим любую клетку после первых 4к шагов — теперь у нас за один шаг покрывается целый столбец или целая строка, так вот если покрывается столбец или строка, то в следующий раз он покроется не больше чем через 4к шагов — это можно доказать из того, как смещаются покрываемые столбцы и строчки относительно начальной позиции — для столбцов (0, +2, -2, +4), для строк (-1, 2, -3, 4) — такая последовательность задает равномерное покрытие

У нас зашел. Такой код на Яндекс.Контесте работает 442мс.

Дай знать, если зайдет в дорешку =)

H: Проведём рёбра от i к f(i). Для каждого снека выберем одно входящее ребро, с помощью которого можно получить выгоду (если их несколько — наибольшую). Пока все снеки есть хотя бы по одному, набираем. Потом может возникнуть проблема — граф с выбранными рёбрами может образовывать цикл, и взять все снеки, используя эти рёбра, не получится. Тогда постараемся минимизировать убыток в этом цикле. Рассмотрим каждый снек, прибылью которого мы жертвуем. Мы можем либо не взять его совсем, либо взять с помощью другого менее выгодного ребра, ведущего к нему, не входящего в цикл, если такое существует. Прибавляем к ответу прибыль по всему циклу, минимальный убыток отнимаем. В цепочках проблем нет, просто прибавляем суммарную прибыль от них.

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

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

1) Перебираем все возможные строки-кандидаты на ответ. Их мало (совсем верхняя граница говорит 18*200, но если рассматривать лишь различные, и смотреть на число символов, их будет мало)

2) Пишем динамику за n^3 / len: dp[i][j]=можно ли получить из пустой строки подстроку с i по j. Переход с помощью вспомогательной динамики dp2[j]: можно ли при фиксированном i получить строку i..j (считаем, что (j-i-1) % len + 1 символов относятся к самой "первой", внешней, строке, из которой получаем i..j).

Заходит за 50 мс.

У меня решение аналогично решению Ильи + оптимизация, что если число букв в строке которую проверяем не матчится с числом букв на отрезке, то сразу говорим ответ. code Кто-то умеет делать для этого тесты, чтобы оно работало хоть как-то долго? (В Я.контесте зашло за 7ms.)

B is a slightly harder version of my old problem: http://acm.sgu.ru/problem.php?contest=0&problem=309 . In this problem you have to be a bit more careful, but the idea is the same: binary search + the idea that with 3 squares at least one of the squares has both sides on the border of the enclosing rectangle.