Разбор задач олимпиады по информатике: алгоритмы

Решение

Наивное решение — перебрать все пары — работает за O(n²). При n до 10⁵ это около 10¹⁰ операций и по времени не проходит.

Идея: пройти массив один раз, храня уже встреченные числа в хеш-множестве. Для текущего элемента x проверяем, встречалось ли ранее число S − x.

Если S − x уже в множестве — пара найдена. Иначе добавляем x в множество и идём дальше.

Проверка в хеш-множестве и добавление — в среднем за O(1), поэтому весь алгоритм работает за O(n).

Краевые случаи: элементы должны быть разными по позиции — но так как мы проверяем S − x до добавления x, один и тот же элемент дважды не учитывается.

Решение

Обозначим dp[i] — число способов добраться до ступени i. На ступень i можно попасть либо с i − 1 (шагом 1), либо с i − 2 (шагом 2).

Значит dp[i] = dp[i − 1] + dp[i − 2]. Это переход динамического программирования.

База: dp[0] = 1 (один способ «никуда не идти»), dp[1] = 1 (единственный шаг на 1).

Считаем по порядку. Для n = 5: dp[2] = 2, dp[3] = 3, dp[4] = 5, dp[5] = 8.

Ответ для n ступеней — dp[n]; последовательность совпадает с числами Фибоначчи. Время O(n), память можно сократить до двух последних значений — O(1).

Решение

Отвечать на каждый запрос прямым суммированием — это до O(n) на запрос и O(n·q) суммарно, что при 10⁵ запросах не проходит.

Идея: заранее посчитать префиксные суммы. Пусть p[0] = 0 и p[i] = a[1] + a[2] + … + a[i]. Тогда p считается за O(n) одним проходом: p[i] = p[i − 1] + a[i].

Сумма на отрезке [l; r] выражается через префиксы: sum(l, r) = p[r] − p[l − 1].

Каждый запрос теперь — одно вычитание, то есть O(1). Все q запросов — за O(q).

Краевой случай: для l = 1 используем p[0] = 0, поэтому отдельной обработки начала массива не требуется.