Найти арифметическую последовательность в массиве чисел

Это достаточно интересная задача. Код я принципиально писать не буду, но с этими мыслями написать его будет не сложно. P.S. если порядок не важен и можно отсортировать то всё будет немного проще.

Мысль 1. У нас 2n чисел, нужно найти из них n. При случайном выборе 2 чисел шанс, что они оба из последовательности, не меньше 1/4. Таким образом, за небольшое число попыток (ну пусть за 20 если совсем не везёт) мы можем найти 2 элемента прогрессии.

Мысль 2. У нас есть два числа в прогрессии. c и d. Очевидно, что d = c + kx. Возьмём разность d-c (или c-d не то что бы важно, но с положительными числами работать чуть приятней). d-c = kx. Число всех делителей числа обычно оценивают как кубический корень из числа. Оценка квадратный корень очевидна, но кубический обычно адекватна. Переберём все делители в поисках x.

Мысль 3. У нас есть число и шаг. Осталось как-то быстро находить есть ли следующее число в нужном направлении и посчитать число таких чисел. Для простоты рассмотрим шаг вперёд. У нас есть a в позиции i и мы ищем a+x правее i. Давайте оценим лобовое решение с циклом. ~ 20 * 10^3 * 100k ~ 2kkk и это уже можно пытаться пропихнуть (там скорее всего будет не 20 и не 10^3 а меньше). Но для ускорения можно попробовать сделать HashMap <Int, list> где для каждого числа есть места где он был, там можно бинарным поиском найти нужное значение. Т.е. что-то в стиле lower_bound(map[a+x], i+1)

Общую сложность оценить очень сложно, но успевает с запасом. Попробуйте строго вывести оценку по времени.

Код вставки в псевдостиле, не стал писать в сишном стиле, но идея надеюсь понятна.

Программа решает задачу за O(nlogn):

import collections


def close_diffs(a):
    for d in (1, 2):
        yield from ((a[i + d] - a[i]) for i in range(len(a) - d))


def diffs(a):
    return sorted(
        ((c, d) for d, c in collections.Counter(close_diffs(a)).items()),
        reverse=True
    )


def progs(a, d):
    seqs = {}
    for ai in a:
        seqs[ai] = seqs.get(ai - d, 0) + 1
        yield ai, seqs[ai]


def main():
    a = [int(w) for w in input().split()]
    a.sort()

    n = len(a) // 2

    for _, d in diffs(a):
        for last, length in progs(a, d):
            if length >= n:
                print(last - (d - 1) * length, d)
                return


main()

Поиск шага прогрессии

Отсортируем все 2n чисел по возрастанию. Получившуюся последовательность обозначим a_i, 1 ≤ i ≤ 2n. Внутри них прячется арифметическая прогрессия из n чисел. Пусть i_k – индексы членов арифметической прогрессии. Это значит что a_ik+1 - a_ik = d, где d – шаг прогрессии.

Меня интересуют шаги индексов прогрессии: s_k = i_k+1 - i_k, 1 ≤ k ≤ n - 1. Предположим что в прогрессии есть m штук шагов размера три или больше. Тогда сумма всех шагов ∑s_k ≥ n + 2m. Здесь n считает места занятые самими элементами. 2m – оценивает сумму длин промежутков между элементами в шагом три или больше. C другой стороны эта сумма равна разнице между последним индексом и первым. То есть, ∑s_k ≤ 2n - 1. Получили неравенство: n + 2m ≤ 2n - 1. Откуда m ≤ ^{(n - 1)}/₂. Оценим количество шагов размера меньше трёх. Всего шагов n - 1. Тогда коротких шагов:
n - 1 - m ≥ n - 1 - ^{(n - 1)}/₂ = ^{(n - 1)}/₂.

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

Вычислим все разницы a_i+1 - a_i (их 2n - 1 штук) и a_i+2 - a_i (их 2n - 2 штук). Все эти разницы соберём в словарь вида <разница> → <счётчик пар с этой разницей>. В этом словаре нас интересуют только записи в которых счётчик пар не меньше чем ^{(n - 1)}/₂. Таких записей не более чем
^{(4n - 3)}/_{(^{(n - 1)}/2)} = ^{(8n - 6)}/_{(n - 1)} = ^{(8n - 8 + 2)}/_{(n - 1)} = 8 + ²/_{(n - 1)}.

Если n < 4, то всего пар не более 13, а если n >= 4, то пар с большими счётчиками не более 8. Так или иначе у нас есть не очень большое количество чисел-кандидатов в шаги арифметической прогрессии.

Отыскание прогрессии, если шаг задан

Пусть задан шаг прогрессии d. Заведём словарь <последнее значение в прогрессии> → <длина прогрессии>. Сначала словарь пуст. Перебираем значения a_i.
Если в словаре есть ключ a_i - d, то заводим ключ a_i в котором длина увеличена на единицу. Если в словаре нет ключа a_i - d, то заводим ключ a_i в котором длина равна единице.

После окончания итерации (или в процессе) отыскиваем прогрессию максимальной длины. Прогрессия найдена за линейное время.

Общая сложность алгоритма (отыскание кандидатов и отыскание прогрессий для всех кандидатов) – O(nlogn + 8n).

Посмотрим, что нам подсказывают составители задачи: размер задачи 100000 говорит о том, что общий метод нахождения длиннейшей арифметической. последовательности (АП), у которого квадратичная сложность - не подойдёт. Был бы линейный - они бы миллион элементов предложили. Так что стоит ожидать, что существует алгоритм поиска АП как минимум нужной длины со временем порядка O(nlogn).

Ну я, как обычно, как Шариков - "Взять всё, да поделить!"

Разделим массив на две равные части. По крайней мере в одной части есть АП длиной n/2 (этих АП может быть несколько). Для каждой проверим, продолжается ли она в другой части. Если да, и получается общая длина не менее n, то мы нашли искомое.

Рекурсивно делим половинки на четвертинки, где ищем АП длиной n/4, и так далее, до длины частей от 2 до 4, которые обрабатываем специальным образом (для 4 у меня размашисто получилось).

Для 100000 работает не более секунды.

# progression = tuple(startindex, d, size)

def arprogs(a, l, r, size):
    if r-l == 3:
        A,B,C,D = a[l],a[l+1],a[l+2],a[l+3]
        if B-A==C-B and D-C==C-B:
            return [(A,B-A, 4)]
        elif B-A==C-B:
            return [(A,B-A,3), (A,D-A,2), (B,D-B,2), (C,D-C,2)]
        elif B-A==D-B:
            return [(A,B-A,3), (A,C-A,2), (B,C-B,2), (D,D-C,2)]
        elif C-A==D-C:
            return [(A,C-A,3), (A,B-A,2), (B,C-B,2), (B,D-B,2)]
        elif C-B==D-C:
            return [(B,C-B,3), (A,B-A,2), (A,C-A,2), (A,D-A,2)]
        else:
            return [(A,B-A,2), (A,C-A,2), (A,D-A,2), (B,C-B,2), (B,D-B,2),(C,D-C,2)]
    if r-l == 2:
        if a[l]+a[r]==2*a[l+1]:
            return [(a[l],a[l+1]-a[l], 3)]
        else:
            return [(a[l],a[l+1]-a[l], 2), (a[l],a[l+2]-a[l], 2), (a[l+1],a[l+2]-a[l+1], 2)]
    if r-l == 1:
        return [(a[l],a[l+1]-a[l], 2)]

    result = set()

    m = (l + r) // 2
    left = arprogs(a, l, m, size//2)
    right = arprogs(a, m+1, r, size//2)

    for p in left:
        sz = p[2]
        d = p[1]
        next = p[0] + d * sz
        for i in range(m+1, r+1):
            if a[i] == next:
                sz += 1
                next += d
        if sz >= size:
            result.add((p[0], d, sz))

    for p in right:
        sz = p[2]
        d = p[1]
        prev = p[0] - d
        for i in range(m, l-1, -1):
            if a[i] == prev:
                sz += 1
                prev -= d
        if sz >= size:
            result.add((prev+d, d, sz))

    return result

from random import randint
n = 20 #100000
a0 = randint(1,n)
d = randint(-n//6,n//6)
a = []
for i in range(n//2):
    a.append(a0 + i*d)
print(a0, d)
for i in range(n//2):
    a.insert(randint(0, len(a)), randint(-n, n))
#print(a)
print(arprogs(a, 0, n-1, n//2))

10 -2
[10, 1, 8, 6, 4, -17, 8, 2, -15, -19, 8, 0, 7, -9, 1, -2, -18, -4, -6, -8]
{(10, -2, 10)}

1. Сортируем исходный массив A{i}. Время: O(n*log(n))
2. Cоставляем список расстояний между соседними точками L1[i] = A[i+1]-A[i]. O(n)
3. Сортируем L1. O(n*log(n)).
4. Если (отсортированный) список L1 содержит n/2 нулей - то в A содержится n/2 совпадающих чисел. Достаточно проверить числа в середине (отсортированного) массива A и на его концах. O(1).
5. Cоставляем список расстояний между соседями соседей L2[i] = A[i+2]-A[i]. O(n)
6. Сортируем L2. O(n*log(n)).
7. Сливаем сортированные массивы L12 = merge_sorted(L1, L2). O(n) Теперь в массиве L12 есть не менее n/2-1 совпадающих чисел, равных шагу искомой последовательности, при том что последовательность L12 имеем длину 4*n-3. Т.е. имеем не более 8 числе-кандидатов на шаг прогрессии. В списке L12 так много искомых чисел, потому что членами прогрессии являются не менее половины исходной последовательности, и остатка недостаточно чтобы вставить по 2 и более точек между соседями.
8. Составляем список кандидатов на шаг прогрессии. O(n) (Один проход по L12.)
9. Для каждого кандидата d, (перебираем в порядке возрастания d):
   • Составляем массив остатков от деления В[i] = A[i] %d O(n)
   • Сортируем B. O(n*log(n)), если d-искомый, от массиве B не менее совпадающих чисел. т.е. не более 2 кандидатов на остаток от деления с.
   • Для каждого кандидата на остаток от деления c:
     • Составляем список D = [ Ai for Ai in A if Ai %d == c ] O(n) В этом списке члены искомой прогрессии идут подряд, хотя, возможно, на концах есть члены не входящие в прогрессию.
     • Проверяем что в D содержится искомая подпоследовательность O(n). Выходим из циклов, если нашли ответ.

Итого: O(n*log(n))

P.S.

Данный алгоритм будет работать, при условии что все числа прогрессии, а также шаг арифметической прогрессии представимы в числах с плавающей точкой точно.