Просьба посмотреть эту задачу:
http://acm.timus.ru/problem.aspx?space=1&num=1395

Я придумал достаточно быстрый алгоритм, требующий O(N^2) времени, но расходующий O(N^2) памяти. У меня прога еле влезла в лимит памяти варианта 1 данной задачи. У меня было дерево, узлы которого - байты числа. Поиск числа по нему занимал 4 итерации, т.е. не зависел от количества чисел. Для каждых двух чисел я по дереву определял, существует ли третье число в массиве. Эти данные заносились в двухмерный массив и затем вычислялась максимальная цепочка. Т.о. работало за O(N^2) шагов и требовало O(N^2) памяти (массив+дерево).
У меня вопрос, каким образом можно выделить самую длинную арифметическую прогрессию из последовательности чисел за O(N^2) операций, тратя при этом O(N) памяти?

Это сообщение отредактировал(а) CPlusPlusFAN - 5.4.2008, 01:41

А где найти часть 1 задачи? Я написал простое решение за N^2, хотел проверить его, и только потом улучшать потребление памяти, а тут оказывается, что субмитить "часть 1" нельзя :(

Моё решение - для каждой пары (i,j) за О(1) движущимся указателем искать следующий элемент k в арифметической прогрессии. Пока я записал его в очевидной форме с двумерными массивами, но есть подозрение, что если изменить порядок вычислений, то двумерных массивов можно избежать.

Имею мысль, что сложность O(N^2) не пройдет по времени.

Добавлено через 21 секунду
Надо линейно или за O(N*log N)

Добавлено через 1 минуту и 38 секунд


Там же есть ссылка...

Добавлено через 6 минут и 3 секунды
хм...

PPS05
Ага, я тоже форум прочитал, поэтому и надеялся, что чистый N^2 пройдёт 
Вообще, 100 миллионов по идее должно впритык влазить в 1 секунду...

Мда, а ссылку на первую часть как-то я не заметил )))
Искал "часть 1" через гугл, он нашёл что-то не то )

[added]
Да, что-то первая часть со скрипом прошла 
0.2 сек

Это сообщение отредактировал(а) maxdiver - 8.4.2008, 15:08

Я достаточно учавствовал на подобных олимпиадах, обычно на секунду давали порядка 10^7 - не больше. Может у них комп мощнее... Смотрел статистику? 0.2 сек для N^2 как-то уж быстро. Я было даже сел писать динамику, но понял, что неправ, хотя скорее именно динамикой и решается.

Добавлено через 8 минут и 26 секунд
Во всяком случае, мои надежды на то, что "влезет" всегджа пролетали...   

Народ, не знаете, как её можно решить? Может кто уже решил?

ЗЫ Я уже не надеялся на ответы.  

Вот даже не смотрел. И не буду. Что, запостить условие задачи нельзя было? руки оборвет?