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

Решение.

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

Нумеруем пункты от 0 до N − 1. Расстояние по кольцу между i и j равно min(|i − j|, N − |i − j|). Стоимость F(j) получаем суммированием количества груза aᵢ, умноженного на это расстояние. Сначала непосредственно вычисляем F(0).

Пусть h — целая часть половины N. При переносе центра на один пункт вперёд расстояния до h пунктов позади, включая старый центр, увеличиваются на 1; до h пунктов впереди уменьшаются на 1. При нечётном N остаётся один пункт, расстояние до которого не меняется. Храним суммы грузов increasing и decreasing в этих группах. Новая стоимость равна старой плюс increasing минус decreasing.

После сдвига обновляем обе суммы: из каждой группы выходит один пункт и входит один пункт. Индексы берём по модулю N, чтобы корректно перейти через начало кольца. Вместе с начальным центром выполняем N − 1 переходов и сравниваем все N стоимостей. Формула работает и для чётного, и для нечётного N; прямой пересчёт стоимости в найденном пункте проверяет итог.

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

from array import array

def solve(name):
    with open(name, encoding="utf-8-sig") as f:
        n = int(f.readline())
        a = array("q", (int(f.readline()) for _ in range(n)))

    half = divmod(n, 2)[0]
    cost = sum(value * min(i, n - i) for i, value in enumerate(a))
    best = cost
    increasing = sum(a[i % n] for i in range(1 - half, 1))
    decreasing = sum(a[1:half + 1])
    for center in range(n - 1):
        cost += increasing - decreasing
        best = min(best, cost)
        increasing += a[(center + 1) % n] - a[(center - half + 1) % n]
        decreasing += a[(center + half + 1) % n] - a[(center + 1) % n]
    return best

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

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

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

Для указанных пунктов стоимость дополнительно вычислена прямым суммированием кратчайших расстояний по кольцу. Независимый расчёт через удвоенную последовательность и взвешенные префиксные суммы дал тот же минимум.

Ответ: 141530 18192010182272.