509A - Максимум в таблице

В этой задаче нужно было сделать то, что написано в условии: построить таблицу(двумерный массив) по указанным правилам и найти максимум в таблице.

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

Также проходило и просто решение рекурсией:

def elem(row, col):
    if row == 1 or col == 1:
        return 1
    return elem(row - 1, col) + elem(row, col - 1)

Кроме того, можно было заметить в таблице Треугольник Паскаля и понять, что ответ — это

Готовил: riadwaw
Разбор от: riadwaw

509B - Раскраска шаров

Пусть найдутся две кучки, в которых количество камней отличается строго больше чем на k, тогда решения не существует:

Пусть теперь M = max a_i ≤ min a_i + k = m + k, покажем, как построить правильную раскраску:

• покрасим по m камней в каждой кучке в первый цвет
• в каждой кучке все оставшиеся камни покрасим в любые различные цвета(можно использовать первый еще один раз) (это можно сделать т.к осталось не более k камней.

Заметим, что 1-ый цвет встречается в каждой кучке m или m + 1 раз, а остальные цвета — 0 или 1 раз

Готовил: Kostroma
Разбор от: riadwaw

509C - Суммы цифр

Будем действовать жадно. На первом шаге найдём минимальное число b₁ с суммой цифр a₁. Далее, на i-м шаге найдём минимальное число b_i с суммой цифр a_i, которое больше чем b_i - 1.

Почему это правильно? Поскольку b₁ — минимальное число с суммой цифрой a₁, то первое число не меньше чем b₁. Далее по индукции: i-е число не меньше b_i, поэтому (i + 1)-е число должно иметь сумму цифр a_i + 1 и быть больше чем b_i. Но минимальное такое число как раз b_i + 1. Значит, построенный пример даёт оптимальное решение задачи.

Осталось научиться решать подзадачу: найти минимальное число с суммой цифр x, которое больше y. Она решается стандартным подходом: идем по цифрам числа y с младших разрядов и пытаемся увеличить соответствующую цифру (считаем, что каждое число содержит бесконечно много нулей слева от своей старшей цифры). Пусть справа осталось k цифр, тогда сумма этих k цифр может быть любым натуральным числом от 0 до 9k. Если получилось увеличить текущую цифру так, что при каком-то выборе цифр справа от неё получилась сумма x, то мы получили ответ. Заметим, что цифры справа от текущей позиции в таком случае нужно заполнять жадно с младших разрядов, каждый раз используя максимально возможную цифру — таким образом мы действительно получим минимальный ответ.

Оценим максимальную длину ответа, т.е. числа b_n. Заметим, что если длина десятичной записи b_i хотя бы 40, то в промежутке между 10^k и 10^k + 1, где k — наименьшее натуральное число, такое что 10^k ≥ b_i, есть числа со всеми суммами цифр от 1 до 9k. Так как все a_i ≤ 300, то при в отрезке [10^k, 10^k + 1] есть любая из интересующих нас сумм цифр. Значит, при достижении 40-значного числа на каждом шаге количество цифр в десятичной записи b_i увеличивается не более чем на 2, а значит итоговый ответ будет иметь десятичную записать не длиннее 640 цифр (еще немного подумав, можно понять, что эту оценку можно усилить до 340).

Значит, получаем решение за O(n·maxLen), где maxLen — максимальная длина ответа. Поскольку n ≤ 300, maxLen ≤ 640, такое решение с запасом проходит.

Готовил: Endagorion
Разбор от: Kostroma

509D - Восстановление чисел

Заметим, что если в корректном ответе ко всем b_i добавить 1, а из всех a_i вычесть 1 (и при необходимости добавив k), то ответ останется корректным. поэтому можно считать, что a_i = 0, тогда из первой строки однозначно восстанавливаются b_j, а по ним — a_i (Можно пока разрешить им быть отрицательными, а потом добавить нужное число раз k). Теперь для любых i, j мы можем найти "ошибку" .

Если все ошибки нулевые — всё отлично, возьмем k достаточно большим и ответ будет автоматически корректным.

Для того, чтобы не нарушалось условие в клетке (i, j) необходимо и достаточно, чтобы e_i, j делилось на k. Таким образом, k должно быть делителем gcd_i, j(e_i, j). При этом, k должно быть строго больше, чем все числа в таблице. Таким образом выгодно попытаться поставить k = gcd_i, j(e_i, j), что можно сделать, если k > max_i, j(w_i, j). В противном случае ответа не существует.

Готовили: Kostroma, riadwaw
Разбор от: riadwaw

509E - Мелодичная песня

Посчитаем суммы vowel(s_i) на всех префиксах строки, чтобы за O(1) можно было легко посчитать сумму vowel(s_i) на любой подстроке.

Будем перебирать m с 1 до . При фиксированном m найдем сумму простых мелодичностей всех подстрок длины m. Для этого посмотрим, сколько раз i-й символ s входит в эту сумму.

При m = 1 каждый символ входит ровно один раз. При m = 2 все символы, кроме крайних — 2 раза, крайние 1 раз. При m = 3 все 3 раза, кроме второго и предпоследнего(2 раза) и первого и последнего (1 раз).

При m = |s| каждый символ входит один раз, как и в случае m = 1, а при m = |s| - 1— 2 раза кроме крайних, как и в случае m = 2.

В общем случае, i-й символ входит min(m, |s| - m + 1, i, |s| — i + 1) раз. Можно заметить, что при переходе от m к m + 1 к сумме прибавляются вхождения символов на подотрезке с m по |s| - m + 1(если m > |s| - m + 1, то убавляются на подотрезке с |s| - m + 1 по m).

Таким образом, можно легко пересчитать сумму вхождений гласных при переходе от m к m + 1, прибавив(убавив) сумму vowel на подстроке. Итоговое решение за O(N).

Готовил: zemen
Разбор от: zemen

509F - Контроль успеваемости

Рассмотрим произвольное дерево на n вершинах. Подвесим дерево за вершину 1, и пусть массив a — результат работы dfs-а. Тогда вершины поддерева с вершиной v, 1 ≤ v ≤ n, записаны в подмассив a[l_v..l_v + size_v - 1], где l_v есть позиция вершины v в массиве, а size_v — размер поддерева.

Решим задачу, используя сей факт и ДП на подотрезках. Пусть задан массив a, и пусть e[l, r] есть количество деревьев, составленных из вершин a[l], a[l + 1], ..., a[r], т.ч. dfs, запущенный из вершины a[l], выведет вершины в том же порядке, в котором они представлены в массиве a. Тогда, если l = r, то e[l, r] = 1; иначе , где сумма берется по всем возможным множествам детей a[l], т.е. по всем таким k;pos₁, ..., pos_k + 1, что l + 1 = pos₁ < pos₂ < ... < pos_k + 1 = r + 1, 1 ≤ k ≤ r - l, a[pos₁] < a[pos₂] < ... < a[pos_k] (вспомним, что в dfs-е дети перебираются в порядке возрастания). Однако даже при наличии ответов для подотрезков отрезка [1..n] решение с использованием такой формулы будет работать экспоненциально долго.

Финальная идея заключается во введении d[l, r]:  = e[l - 1, r], 2 ≤ l ≤ r ≤ n. Действительно, из вышеприведенной формулы следует, что d[l, r] = ([утверждение] определим как 1, если утверждение истинно, и 0, если ложно), а также e[l, r] = d[l + 1, r]. Таким образом, d[l, r] и e[l, r] для каждого отрезка вычисляются за линейное время; ответом же на задачу является e[1, n]. Итоговая асимптотика решения O(n³).

Готовил: DPR-pavlin
Разбор от: DPR-pavlin