Задание EGEINFA47CA1: Эффективная обработка данных и кластеры

Решение.

Обрабатываем два приложенных текстовых файла отдельно. В файле A содержится 9965 записей, в файле B — 1999955. Заголовок задаёт параметры и не является элементом последовательности. Порядок исходных записей сохраняем. Числа из иллюстративного примера не заменяют данные файлов.

Ищем отрицательную нечётную сумму. Положим vᵢ = −aᵢ: теперь нужна положительная нечётная сумма, а длина отрезка не меняется. Строим P₀ = 0 и префиксные суммы v. Для отрезка от l + 1 до r нужно Pₗ < Pᵣ. Неравенство строгое: нулевая сумма не подходит.

Для нечётной разности префиксы должны иметь разную чётность. Разделим возможные левые префиксы по чётности. В каждом списке оставим только очередные строгие рекорды уменьшения P. Если более ранний префикс той же чётности не больше нового, новый можно отбросить: ранний подходит не хуже и даёт большую длину при любом будущем правом конце.

Просматриваем правые концы r от N к 1. В нужном списке левых префиксов значения строго убывают. Пока последний префикс меньше Pᵣ, снимаем его и проверяем длину r − l. Это самый правый ещё возможный конец для снятого l; дальнейшие меньшие r уже не улучшат длину для него. Если условие не выполнено для последнего, оно не выполнено и для остальных с большими значениями. Отрицательные разности индексов не улучшают начальный ответ ноль. Каждая позиция добавляется и снимается не более одного раза.

Распакуем архив и положим указанные в программе текстовые файлы рядом с ней. Программа печатает результат для A, затем для B:

from array import array

def solve(name):
    sign = -1
    parity = 1
    prefix = array("q", [0])
    with open(name, encoding="utf-8-sig") as f:
        n = int(f.readline())
        for _ in range(n):
            prefix.append(prefix[-1] + sign * int(f.readline()))
    stacks = [array("I"), array("I")]
    for i, value in enumerate(prefix):
        stack = stacks[value % 2]
        if not stack or value < prefix[stack[-1]]:
            stack.append(i)
    best = 0
    for r in range(n, 0, -1):
        stack = stacks[(prefix[r] % 2) ^ parity]
        while stack and prefix[stack[-1]] < prefix[r]:
            l = stack.pop()
            best = max(best, r - l)
    return best

print(solve('349_27_A.txt'), solve('349_27_B.txt'))

Время O(N), память O(N). Считывание и все арифметические действия выполняются над целыми числами; округление вычисленных ответов не требуется.

Проверка на исходных файлах. Номера элементов ниже отсчитываются от 1; полный алгоритм проверяет все допустимые варианты, а указанные позиции показывают достижение найденного результата.

Для каждой строки длина равна конец − начало + 1. Суммы имеют требуемый знак и чётность. Максимальность длин подтверждена полным проходом по правым концам и независимым упорядочением префиксов.

Ответ: 5957 1199892.