1. Одежда (A Div-2)
В этой задаче ограничения позволяли просто перебрать все возможные тройки i, j, k (которых не больше, чем 1003 = 1000000), для каждой тройки проверить, все ли элементы тройки подходят друг к другу, и среди троек, в которых все элементы подходят друг к другу, найти тройку с минимальной суммой ai + aj + ak.
2. Сумма цифр (B Div-2)
Изначально в числе не больше, чем 100000 цифр. Значит, после первого применения заклинания сумма цифр будет не больше, чем 9· 100000 = 900000, ее можно сосчитать простым проходом по строке из ввода. Значит, в нем будет не больше 6 цифр. После второго применения заклинания число станет не больше, чем 9· 6 = 54. То есть, число будет не более, чем двухзначным. Сумма цифр двузначного числа не больше 18, а сумма цифр числа, которое не больше 18, уже однозначна. Значит, Геральд сможет применить заклинание не больше 4 раз. При этом, чтобы первый раз посчитать сумму цифр нам понадобится 100000 сложений, а остальные действия незначительны.
3. Домашнее задание (C Div-2, A Div-1)
Для каждой буквы найдем количество раз, которое она встречается. Пусть 'a' встречается ka раз, 'b' встречается kb раз, и так далее. Наша задача --- выкинуть все вхождения как можно большего количества букв. Пусть мы выкинули какие-то x букв. Заметим, что если вместо этого выкинуть x самых редких букв, суммарное число выкинутых букв будет не больше. Значит, для любого числа x легко выяснить, можно ли удалить все вхождения каких-нибудь x букв. Соответственно, можно выбрать минимаьное такое x, для которого можно.
4. Автобусы (D Div-2, B Div-1)
Давайте для каждой остановки x от 0 до n посчитаем величину kx - количество способов на нее приехать. Рассмотрим i-тый автобус. Количество способов приехать на остановку ti на i автобусе, очевидно, просто равно количеству способов сесть в этот автобус. А сесть в этот автобус можно на остановке si, si + 1, ..., ti - 1. Таким образом, количество способов приехать на остановку ti на i автобусе равно сумме ksi + ksi + 1 + ... + kti - 1. Осталось заметить, что, чтобы найти общее количество способов попасть на остановку ti, надо просуммировать количества способов попасть на нее на каждом автобусе, у которого это конечная остановка.
Осталось решить две проблемы. Проблема первая: 0 ≤ n ≤ 109, поэтому все kx в память не влезут. Но, очевидно, нам понадобятся только остановки с ненулевым kx. Например, можно сжать координаты: создать список из всех встречающихся в условии остановок (а так же остановок 0 и n), отсортировать его, убрать повторяющиеся и заменить каждый номер остановки на его индекс в этом массиве. Тогда получится, что все остановки имеют номера в пределах 200001. Массив такой длины уже спокойно влезает в память.
Второе, если сумму ksi + ksi + 1 + ... + kti - 1 считать циклом, решение будет работать за O(m2), что не влезает в TL. Эта проблема тоже легко решается: можно создать и обновлять одновременно с массивом k[] массив sum[], в котором будем сумму элементов k до некоторого момента: sum[i] = k[0] + k[1] + ...\ + k[i - 1]. Иными словами, sum[0] = 0, sum[i + 1] = sum[i] + k[i]. Тогда количество способов доехать до остановки ti на i автобусе будет равно sum[ti] - sum[si].
Итого, сложность решения, O(m*log(m)) времени (за счёт сжатия координат), O(m) памяти.
5. Вектора (E Div-2, C Div-1)
Переформулируем задачу в комплексных числах.
Рассмотрим комплексные числа a = xA + iyA, b = xB + iyB и c = xC + iyC. С числом A разрешается делать операции A → A + C и A → iA.
Посмотрим, что может получится из числа A при применении к нему этих операций. Поскольку i4 = 1, то полученное число имеет вид A· ik + aC + biC - cC - idC для каких-то целых неотрицательных k, a, b, c, d, или, иными словами, A· ik + aC + biC для k = 0, 1, 2, 3 и целых a, b. Поскольку k может быть равно только 0, 1, 2 или 3, достаточно узнать, можно ли представить одно из чисел B - A, B - iA, B + A или B + iA в виде aC + biC.
Осталось научиться понимать, представляется ли некоторое комплексное число D в виде aC + biC. Запишем в виде системы линейных уравнений:
a· xC - b· yC = xD
a· yC + b· xC = yD
Решить систему линейных уравнений - это уже стандартная техническая задача.
6. Замок (D Div-1)
Перенумеруем вершины так, чтобы стартовая вершина, в которой исходно находится Геральд, получила номер 0.
Подвесим дерево, о котором идет речь в задаче, за вершину 0, и рассмотрим прямых потомков этой вершины. Пусть Геральд начал свой путь, пойдя в одну из этих вершин - вершину x. Далее после этого он должен обойти все поддерево этой вершины и вернуться в нее - иначе его маршрут пройдет не по всем вершинами. Далее он вернется из вершины x в вершину 0 и больше никогда не вернется в эту вершину. Далее он пойдет еще в какого-то предка вершины 0 (если, конечно, они у нее еще есть), и обойдет поддерево, подвешенное на эту вершину; и так далее. Пусть мы посчитали искомую величину для аналогичных задач на поддеревьях. Попробуем исходя из этого посчитать искомую величину для всего дерева. Это даст нам возможность решать задачу динамикой по поддереву.
Пусть у вершины 0 n сыновей. Пусть в них k1, k2, ..., kn потомков (включая них самих).
Пусть всего в дереве N вершин.
Пусть Ti - это удвоенная сумма длин всех ребер в i-том поддереве, включая ребро, ведущее в вершину 0. Это величина - ровно то время, которое потребуется Геральду, чтобы обойти все поддерево, начиная из вершины 0 и вернуться в вершину 0.
Наконец, пусть ti - ответ для подзадачи в i-той поддереве. Сразу прибавим к этому времени длину ребра между вершиной 0 и ее i-тым предком. Таким образом, это будет среднее время для поддерева с учётом того, что надо ещё дойти до него от вершины 0.
Пусть мы обошли поддеревья в порядке 1, 2, ..., n. Каково среднее время нахождения клада?
С вероятностью 
клад окажется в первом поддереве. Тогда среднее время нахождения клада будет t1.
клад окажется в первом поддереве. Тогда среднее время нахождения клада будет t1.С вероятностью 
клад окажется во втором поддереве. Тогда среднее время нахождения клада будет T1 + t2.
клад окажется во втором поддереве. Тогда среднее время нахождения клада будет T1 + t2.И так далее. Таким образом, среднее время нахождения клада будет
Посмотрим, можно ли улучшить это время? Поменяем местами поддеревья номер i и i + 1. Тогда из суммы исчезнет слагаемое ki + 1Ti и появится слагаемое kiTi + 1. То есть, сумма изменится на kiTi + 1 - ki + 1Ti. Сумма уменьшится, если это изменение меньше 0, то есть, если kiTi + 1 - ki + 1Ti < 0, что равносильно 
.
.Таким образом, среднее время нахождения клада уменьшить не удастся, если поддеревья отсортированы в порядке возрастания величины 
, иначе найдется пара соседних поддеревьев, замена местами которых приведёт к улучшению результата. Таким образом, надо отсортировать поддеревья по этой величине, и обходить их этом порядке.
, иначе найдется пара соседних поддеревьев, замена местами которых приведёт к улучшению результата. Таким образом, надо отсортировать поддеревья по этой величине, и обходить их этом порядке.7. Конфеты и Камни. (E Div-1)
Суть задачи в том, что есть доска n × m, на которой расставлены числа. И надо пройти от клетки (0, 0) до клетки (n - 1, m - 1), делая шаги на одну клетку вверх или вправо (то есть, увеличивая на 1 одну из координат) так, чтобы сумма чисел на клетках пути была максимальна.
Наша задача определить n + m - 1 клетку оптимального пути. Давайте начнем с малого: определим одну клетку этого пути, а именно среднюю. Пусть 
. Какие клетки поля могут быть k-тыми? Очевидно, те, у которых сумма координат равна k, то есть, это будет диагональ прямоугольника. Поэтому очевидно, что несложно динамикой за O(nm) в нижнем треугольнике под этой диагональю посчитать, какое какую максимальную сумму можно набрать, придя в каждую из клеток этой диагонали. Аналогичной динамикой в верхнем треугольнике (на это раз сверху вниз) для каждой клетки на этой диагонали посчитаем, какую максимальную сумму можно собрать, стартовав с этой клетки. Сложив эти две величины, получим, какую максимальную сумму можно получить, пройдя через эту клетку. Осталось найти клетку (x, y), в которой достигается максимум. Её мы и возьмем за k-тую клетку нашего пути. Заметим, что в течение этой итерации мы использовали O((n + m)2) времени и O(n + m) памяти.
. Какие клетки поля могут быть k-тыми? Очевидно, те, у которых сумма координат равна k, то есть, это будет диагональ прямоугольника. Поэтому очевидно, что несложно динамикой за O(nm) в нижнем треугольнике под этой диагональю посчитать, какое какую максимальную сумму можно набрать, придя в каждую из клеток этой диагонали. Аналогичной динамикой в верхнем треугольнике (на это раз сверху вниз) для каждой клетки на этой диагонали посчитаем, какую максимальную сумму можно собрать, стартовав с этой клетки. Сложив эти две величины, получим, какую максимальную сумму можно получить, пройдя через эту клетку. Осталось найти клетку (x, y), в которой достигается максимум. Её мы и возьмем за k-тую клетку нашего пути. Заметим, что в течение этой итерации мы использовали O((n + m)2) времени и O(n + m) памяти.Теперь рекурсивно перейдем к подзадачам, то есть, будем искать оптимальный путь от клетки (0, 0) до клетки (x, y), и от клетки (x, y) до клетки (n, m).
Осталось убедиться, что такое решение решение занимает ((n + m)2) времени.
Обозначим n + m за r.
На первом уровне рекурсии мы потратим r2 времени. На втором - два раза по 
. На третьем - 4 раза по 
, и так далее. Все будет потрачено времени 
. Таким образом, описанное решение занимает O((n + m)2) времени и очевидно, что оно занимает O(n + m) памяти.
. На третьем - 4 раза по , и так далее. Все будет потрачено времени . Таким образом, описанное решение занимает O((n + m)2) времени и очевидно, что оно занимает O(n + m) памяти.
