Здесь приводится разбор всех задач прошедшего раунда. Вопросы и предложения задавайте в комментариях. Отдельное спасибо пользователю Zlobober за разбор задачи С из первого дивизиона, который я использовал в качестве авторского разбора.

Дивизион 2, задача А. Петя и строки

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

Дивизион 2, задача B. Петя и квадрат

Оказывается, что если мы хотим разделить квадрат на две равные части, то линия разреза должна проходить через центр квадрата. Отсюда становится понятно, что если отмеченная клетка содержит центр квадрата, то ломаную провести невозможно и нужно вывести NO, иначе вывести YES. Получаем код, которой решает данную задачу:

scanf("%d%d%d", &n, &x, &y);

n /= 2;

if ((x == n || x == n + 1) && (y == n || y == n + 1)) printf("NO\n"); else printf("YES\n");

Дивизион 2, задача С. Петя и неравенства (Дивизион 1, задача А)

Нетрудно видеть, что максимум суммы квадратов достигается, когда все числа, кроме одного равны 1. Теперь достаточно проверить, можем ли мы из заданного y набрать n положительных целых чисел и если можем, то проверить, что x ≤ 1 + 1 + ... + (y - (n - 1))².

Дивизион 2, задача D. Петя и делители (Дивизион 1, задача B)

Заведем массив used, такой, что в used[j] хранится номер последнего числа во входных данных, у которого есть делитель j. Тогда для каждого запроса будем последовательно перебирать делители числа x_i и для каждого делителя k числа x_i будем проверять является ли он «уникальным». После этого обновим пометку для делителя k в массиве used.

Дивизион 2, задача E. Петя и пауки (Дивизион 1, задача С)

Данная задача подразумевала множество решений. Следует отметить, что количество входных данных не так велико, поэтому можно было попытаться вручную разобрать все возможные входные данные. Можно было написать перебор, который при нужных отсечениях можно было сдать даже без предпросчета ответов. Однако большинство решений участников все же содержало в себе динамику по профилю. Здесь я приведу решение пользователя Zlobober.

Будем считать не максимальное количество оставшихся клеток, а минимальное количество центров, в которые могут сбежаться все пауки. Повернём доску, чтобы количество строк было не больше шести.

Пусть D[k][pmsk][msk] - это минимальное количество центров, достаточное, чтобы собрать всех пауков с первых k столбцов, причём k-ый столбец имеет маску pmsk, а k + 1-ый - msk. Тогда за переход мы перебираем маску tmsk k - 1-ого столбца, и среди тех, для которых k-ый столбец может целиком разбежаться по центрам, выбираем тот, для которого D[k - 1][tmsk][pmsk] минимально.

Получается решение за O(n*2^3m), где n > m.

Дивизион 1, задача Д. Петя и раскраски

Заметим, что если m = 1, то ответ kⁿ, так как допустимы все возможные раскраски.

Теперь m > 1. Рассмотрим первый столбец доски (проведем вертикальную прямую справа от первого столбца). Пусть в нем x различных цветов. Тогда в оставшихся столбцах тоже x различных цветов по условию. Теперь если мы сдвинем нашу вертикальную прямую на 1 вправо, то количество цветов в левой части не уменьшится, а в правой не увеличится. Повторяя сдвиги, можем сделать вывод, что опять в левой части будет x различных цветов и в правой тоже x. Теперь мы получаем, что в крайних столбцах доски ровно по x различных цветов. Нетрудно видеть, что в остальных столбцах доски должны встречаться только те цвета, которые встречаются в пересечении цветов крайних столбцов доски.

Будем последовательно перебирать два числа x и y, где x - количество используемых цветов в каждом из крайних столбцов, y - количество общих цветов в крайних столбцах. При этом ясно, что на x и y накладываются некоторые ограничения в зависимости от размера доски.  Будем считать ответ для каждой такой пары, а затем все их просуммируем. Тогда для каждой пары (x,y) имеем, что надо сначала выбрать (2x-y) цветов из k данных цветов, которые мы будем использовать при раскраске. Поэтому ответ для пары нужно сразу умножить на C(k,2x-y). Далее, выберем (x-y) уникальных цветов, которые будут использоваться в первом столбце. Ответ умножается еще на C(2x-y,x-y). Выбирая (x-y) уникальных цветов для последнего столбца, имеем еще одно умножение ответа на C(x,x-y). Теперь надо знать, сколько существует способов раскрасить n клеток в x цветов. Это несложная динамика (при этом цвета учитываются лексикографически, что означает, что если на доске есть цвета a и b, при этом a<b, то цвет a встречается раньше чем b), которая пересчитывается по формуле: d[i][j]=j*d[i-1][j]+d[i-1][j-1]. Домножаем ответ для пары на d[n][x] (раскрашиваем первый столбец) и потом еще раз на d[n][x] (раскрашиваем последний столбец). После этого в каждом из крайних столбцов можно сделать перестановку цветов, поэтому нужно ответ умножить на (x!)². Теперь осталось домножить ответ на y^n(m-2), так как цвета в средних столбиках могут быть любыми из пересечения.

Можно привести простой код, который проверяет нужные нам пары:

long long ans=0;

for (int y=0; y<=n; y++){

      long long cur=powmod(y,n*(m-2));

      for (int x=y; x<=n; x++)

      if (2*x-y<=k)

      {

            long long tek=cnk[2*x-y];

            tek*=cnn[2*x-y][x-y], tek%=mod;

            tek*=cnn[x][x-y], tek%=mod;

            tek*=d[n][x], tek%=mod;

            tek*=d[n][x], tek%=mod;

            tek*=f[x], tek%=mod;

            tek*=f[x], tek%=mod;

            tek*=cur;

            ans+=tek;

            ans%=mod;

      }

}

cout<<ans<<endl;

Здесь, cnk[i] – это предпросчитанное C(k,i), cnn[a][b] – C(a,b), d[n][x] – динамика как в разборе, f[x] – x!.

Заметим, что у некоторых участников возникли проблемы с тайм лимитом, однако если аккуратно предпросчитать все C(k,i) и помнить, что нам никогда не понадобится более чем 2000 цветов из предложенных 1000000, то проблем со временем быть не должно. Следует отметить, что авторское решение работало менее 200 мс, при предложенном тайм лимите в 5 секунд.