Арифметическая прогрессия

[Carbon]

Я уже приводил эту задачу, но в другом разделе:

Последовательность S состоит из N элементов S[i], пронумерованных от 1 до N. Из этой последовательности необходимо выбрать максимальное количество различных элементов, являющихся последовательными членами некоторой возрастающей арифметической прогрессии. Порядок этих элементов в последовательности S не имеет значения.

Первая строка содержит целое число N (2<=N<=10000). Вторая строка содержит N целых чисел S[i] (1<=S[i]<=1000000000).

В первую строку вывести максимальное количество элементов. Во вторую строку вывести через пробел и в любом порядке номера этих элементов в последовательности S. Если задача имеет несколько решений, то вывести любое из них.

Лимит времени: 1 с.
Лимит памяти: 4 Мб.

ЗЫ Народ. Не подскажете идею решения. Запрограммировать я и сам смогу.

[B_N]

Как вариант можно
1. организовать массив А из записей
а) коэфф. прогрессии
б) массив/список индексов/элементов исходного массива
в) следующее подходящее для данной прогрессии число

2. Пройтись по заданной строке в поисках элементов, удовлетворяющих условию А.[в)], в случае обнаружения соответственно менять элементы А.[в)] и А.[б)] Самая грубая сложность будет в районе (4998 * 10000) сравнений, можно, конечно оптимизировать, скажем, исходя из того, что в массиве А элементы строго упорядочены.

[Carbon]

А это случайно не O(N^3)?

[B_N]

Сообщение от Carbon

А это случайно не O(N^3)?

С какой стати? нам надо максимум сравнить N элементов входных данных с N/2 элементами, которые мы сами готовим.

[alexBlack]

А сама последовательность никак не задана ?
Например, если отсортированная последовательность

1 2 3 5 7 9 13 17

то арифметическими прогрессиями могут быть:

1 2 3
1 3 5 7 9
1 5 9 13 17

Может так попробовать:

Последовательность отсортировать и найти разность между элементами:

1 1 2 2 2 4 4

Арифметическая последовательность заканчивается (и слева и справа) там, где разность становится больше. Если разность становится
меньше, то заканчивается там, где последовательная сумма разностей больше текущей.

[Carbon]

Сообщение от alexBlack

А сама последовательность никак не задана ?
Например, если отсортированная последовательность

1 2 3 5 7 9 13 17

то арифметическими прогрессиями могут быть:

1 2 3
1 3 5 7 9
1 5 9 13 17

Может так попробовать:

Последовательность отсортировать и найти разность между элементами:

1 1 2 2 2 4 4

Арифметическая последовательность заканчивается (и слева и справа) там, где разность становится больше. Если разность становится
меньше, то заканчивается там, где последовательная сумма разностей больше текущей.

Да последовательность может быть хоть отсортированнной. Проблема в том, что чтобы идти по прогрессии, нужно знать разность. Их O(N^2). Плюс ещё для каждой разности идём по массиву. Вот и O(N^3).

[B_N]

Сообщение от alexBlack

А сама последовательность никак не задана ?

Как я понял, нужно вывести все возможные последовательности.

[B_N]

Carbon, мы ОДИН раз проходим по входным данным. Плюс ко всему, если натыкаемся, например, на число 10, можем не проверять массив А для коэффициентов, больших пяти.

[Carbon]

Сообщение от B_N

а) коэфф. прогрессии

Все коэффициенты? Их O(N^2).

[B_N]

Сообщение от Carbon

Все коэффициенты? Их O(N^2).

Их N/2. Прогрессия же арифметическая.