Для получения максимального возможного результата нужно просто отсортировать слагаемые в порядке неубывания коэффициентов (коэффициенты учитываются со стоящими перед ними знаками + и -). Не нужно обращать внимание на a++ или ++a! Вопрос заключается в том, почему это правильно.

Во-первых, рассмотрим выражение, содержащее только a++. Тогда наше утверждение очевидно: выгодно умножать 'a' на маленькие коэффициенты, пока значение 'a' маленькое, и на большие коэффициенты, когда оно становится больше. То же самое происходит в случае трицательных значений коэффициентов или 'a'. Конечно, это не строгое доказательство. Я надеюсь, что вы еще подумаете над ним, если пока не поняли.

Во-вторых, рассмотрим выражение k*a+++k*++a, где k - некотрый коэффициент, одинаковый для обоих слагаемых. Пусть начальное значение 'a' равно a₀. Вычисляя значение выражения обоими способами, получаем: k * a₀ + k * (a₀ + 2) =  k * (a₀ + 1) + k * (a₀ + 1). Поэтому в данном случае порядок неважен.

В-третьих, пусть наше выражение k*a+++l*++a, где k и l - различные коэффициенты. Это выражение может принимать два разных значения k * a₀ + l * (a₀ + 2) и k * (a₀ + 1) + l * (a₀ + 1). Первое значение больше второго тогда и только тогда, когда k < l. Аналогично можно рассмотреть выражение k*a+++l*++a.

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

Эта задача решается жадно. Будем перебирать заданные числа последовательно, пока не встретим 1. Затем продолжим перебирать числа в поиске числа 2, потом 3, и т.д.

Авторское решение работает за O(n²) по времени и требует O(n²) памяти. Также проходили решения за времени и с O(n) памяти.

Переформулируем задачу. Дано множество отрезков на прямой, и нужно найти максимальное его подмножество, такое, что отрезки в нем не пересекаются 'частично'. Два отрезка [a, b] и [c, d] пересекаются частично, если, например, a < c < b < d.

Возьмем все концы данных трезков, отсортируем их и посчитаем динамику: d_l, r --- максимальный возможный размер подмножества, отрезки в котором не пересекаются частично и расположены между l-м и r-м концом (в отсортированном порядке) включительно. Мы хотим вычислять d_l, r, имея уже посчитанные значения d_i, j для всех l ≤ i ≤ j ≤ r, но [i, j] ≠ [l, r]. Сначала положим d_l, r = d_{l + 1, r}, если мы не берем отрезки с левым концом в l. Если существует отрезок [l, r], мы обязательно включаем его в наше множество. Если мы берем другой отрезок, скажем, [l, i], где i < r, посмотрим на отрезки [l, i] и [i, r] (для них ответ уже посчитан) и попытаемся изменить значение d_l, r. Асимптотика решения O(n²), потому что общее количество левых концов O(n). Затем необходимо вывести сертификат, т.е. само оптимальное множество. Это делается стандартным образом.

Мухи НЕ могут видеть друг друга тогда и только тогда, когда они в противоположных вершинах. Существует  несколько способов проверить это. Например, можно проверить манхеттенское расстояние |x₁ - x₂| + |y₁ - y₂| + |z₁ - z₂| = 3 или евклидово расстояние . Можно проверить, что все три координаты различны (x1 != x2) && (y1 != y2) && (z1 != z2) или просто (x1^x2)+(y1^y2)+(z1^z2) == 3!

Количество способов разложить b предметов по a коробкам, конечно же, a^b. У нас имеется ациклическая игра для двух игроков с состояниями (a, b), для  которых a^b < n. К сожалению, существует бесконечное количество таких состояний: a = 1, b любое. Но в этом случае, если 2^b ≥ n, позиция является ничейной, потому что единственный способ действия для обоих игроков (не приводящий к поражению) - увеличивать b бесконечно.

Другой отдельный случай возникает для позиции с b = 1 и достаточно большого a. А именно, если , имеется также только один ход из этой позиции - увеличивать a. Если a = n - 1, то позиция проигрышная, если a = n - 2 - она выигрышная, при a = n - 3 снова проигрышная и т.д.

Итак, имеется два вида состояний, которые нужно обрабатывать отдельно. Количество остальных состояний не очень большое, и для них можно вычислять стандартную динамику для игр на ациклических графах.

Простое моделирование прыжков лягушек работает слишком долго, потому что n может быть 10⁹. Правильное решение состоит в том, чтобы посчитать для каждой лягушки количество раздавленных комаров путем проверки делимости номеров кочек с комарами на d_i.

Что можно сказать про задачу G? Нужно провести разбор данной функции и вычислить ее значение при всех значениях n. Разумеется, это невозможно сделать путем простой реализации рекурсии, потому что она может работать слишком долго (см. пример с последовательностью Фибоначчи). Поэтому нужно использовать динамическое программирование.

Нужно вычислить все произведения i * j и вывести их в состеме счисления с основанием k.

Рассмотрим только ту часть графа, которая достижима из вершины 1. Задача состоит в том, чтобы найти наибольшее такое t, чо выбранное множество вершин достижимо только в моменты времени, кратные t. Предположим, мы построили искомое множество S₀. Рассмотрим множества S₁, S₂ ..., S_t - 1 всех вершин, достижимых в моменты времени, имеющие остатки 1, 2, ..., t - 1 по модулю t, соответственно. Нетрудно проверить, что эти множества не пересекаются и их объединение совпадает со всем множеством достижимых вершин. Ясно, что ребро из u в v может существовать только в том случае, когда u и v принадлежат последовательным множествам, т.е. , , k + 1 берется по модулю t.

Для каждой вершины v посчитаем расстояние d_v от 1 до v (если существует несколько путей, выберите любой, например, с помощью обхода в глубину). Если из u в v существует ребро, должно выполняться . Анализируя все ребра, мы приходим к заключению, что оптимальное значение t равно наибольшему общему делителю чисел |d_u + 1 - d_v|. Теперь нетрудно райти множетсво S₀.

Самое простое решение - найти два числа l и r - длину наибольшего общего префикса и длину наибольшего общего суффикса двух строк, соответственно. Если l + 1 < n - r, решения нет. Здесь n - длина первой строки. Иначе нужно выдать позиции с max(n - r, 1) до min(l + 1, n). 

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

O(k⁴) и даже некоторые решения за 

O(k⁵) с оптимизациями, но 

KADR предложил решение даже лучше, работающее за

 O(k³) (http://mirror.codeforces.com/blog/entry/793).