I've tried to come up with solution from the story part of the problem, but the worst algorithm I came up with is O(N^4). Is there an O(N^5) algorithm?

My AC solution runs about 10 seconds for test case 1, 2, ...., 2000 on my laptop (it's an old one, though, maybe that's the reason).

How can i improve my O(n ^ 2 * logN) time and O(n * n) memory too pass all tests?
int n, y[2004], index = 1, maximum = 1, rati;
pair<int, int> x[2004];
map<int, int> s[2004];
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> x[i].first;
        x[i].second = i;
        y[i] = 1;
    }
    sort(x, x + n);
    for(int i = 1; i < n; i++)
    {
        for(int j = 0; j < i; j++){
            if(y[i] < s[j][x[i].first - x[j].first] + 2 && x[i].first - x[j].first != 0){
                y[i] = s[j][x[i].first - x[j].first] + 2;
                if(maximum < y[i]){
                    index = i;
                    maximum = y[i];
                    rati = x[i].first - x[j].first;
                }
            }
            s[i][x[i].first - x[j].first] = s[j][x[i].first - x[j].first] + 1;
        }
    }
    cout << maximum << "\n";
    int val = x[index].first, i;
    cout << x[index].second + 1 << " ";
    for(i = index - 1; i >= 0; i--)
    {
        if(val - x[i].first == rati && rati != 0)
        {
            val = x[i].first;
            cout << x[i].second + 1 << " ";
        }
    }
    return 0;
}

dp[i][j]=dp[j][k]+1 where a[j]*2=a[i]+a[k] can be done using a loop.
via: http://www.geeksforgeeks.org/length-of-the-longest-arithmatic-progression-in-a-sorted-array
time O(n^2) space O(n^2)

Can somebody give me some hints on Test 3 ? I get WA but don't know why. I 've run all other test in the forum and it gives right answer

On #1 test my program output:
4
4 5 1 6
with code: cout<<4<<endl<<4<<" "<<5<<" "<<1<<" "<<6
but get wrong answer. Why?

On #1 test my program output:
4
6 1 5 4
but get wrong answer. Why?

Ьудем рассматривать все возможные разности (в виде i-начало, j-конец, i<j) в порядке возрастания. Но запоминать и сортировать их все нет нужды, чтобы получить их, воспользуемся идеей сортировки слиянием: N последовательностей
a(2)-a(1)...a(N)-a(1), a(3)-a(2)...a(N)-a(2) итд, их можно "слить" за O(N^2). Опять-таки, сливать все сразу не надо, надо выделить подряд идущую группу равных элементов (их не более N) и сохранить в промежуточный массив, далее работать с ними, потом брать следующую группу и так пока все сливаемые последовательности не закончатся. Первую группу, где величина разности=0, ессн-но не обрабатываем
Остается из группы k<=N разностей выделить макс.членов арифм.прогрессии, т.е. чтобы конец одной разности = началу другой. Используем массив размера N, где для каждого эл-та исходного массива храним счетчик = длине оканчивающегося в нем куска прогрессии. Первому эл-ту присваиваем счетчик=0. Одним проходом по группе разностей расставляем счетчики
(учитывая что разности изначально сортированы по i-начало в ходе слияния), счетчик[разность.конец]=счетчик[разность.начало]+1, в том же проходе запоминаем наибольший счетчик и последний эл-т, из которых за O(N) легко восстановить всю последовательность. Итого на группу O(k) действий, а в сумме O(N^2)

Can anybody suggest me the 6th test case?

My prog got TLE on test 8
I found that  on test 8 about 0.2 sec  my program spend on reading input data.

Here the part of code ( this part takes about 0.2 sec on test 8 - I checked it many times)
...
  Readln(N);
  for i:=1 to N do
   begin
    A[i].p:=i;
    Read(C);
    A[i].V:=C;
 end;
...



Could you please explain how it should be done?

Edited by author 06.02.2013 14:09

Edited by author 07.02.2013 01:22

Edited by author 07.02.2013 01:22

Why Crash (acces violant)
I use vector < map <int,int> > ! Are the problem in it?

P.S Sorry for my bad English

#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <iostream>
#include <cstdlib>

using namespace std;

struct neww{
 int x,n;
};

int abss(int x)
 {
  if (x>=0) return x;
  else return (-x);
 }

bool funcsort(neww a, neww b)
 {
  if (a.x < b.x) return true;
  else return false;
 }

int main()
{
 int n,i,j,x,maxn;
 neww a[2200];
 scanf("%d",&n);
 vector < map <int,int> > b(12000);
 vector < map <int,int> > pi(12000);
 vector < map <int,int> > pj(12000);

 for (i = 0; i < n; ++i)
     {
      scanf("%d",&a[i].x);
      a[i].n = i + 1;
     }
 sort(a,a+n,funcsort);
 if (n == 1)
  {
   printf("1\n");
   printf("%d\n",1);
   exit(0);
  }

 for (i = n - 1; i >= 0; --i)
   {
      for (j = n - 1; j > i; --j)
         if (a[j].x-a[i].x > 0)
           {
            b[i][a[j].x-a[i].x] = max(b[i][a[j].x-a[i].x],b[j][a[j].x-a[i].x] + 1);
            if (b[i][a[j].x - a[i].x] = b[j][a[j].x-a[i].x] + 1)
             {
              pi[i][a[j].x-a[i].x] = j;
              pj[i][a[j].x-a[i].x] = a[j].x - a[i].x;
             }
           }
   }
 maxn = 0;
 int numb,ost;
 for (i = 0; i < n; ++i)
     for (j = i; j < n; ++j)
            if (b[i][abss(a[i].x - a[j].x)] > maxn)
             {
              maxn = b[i][abss(a[i].x-a[j].x)];
              numb = i;
              ost = abss(a[i].x - a[j].x);
             }
 printf("%d\n",maxn+1);
 printf("%d",a[numb].n);
 while (maxn)
   {
      int nm = pi[numb][ost];
      int ot = pj[numb][ost];

      printf(" %d",a[nm].n);

      numb = nm; ost = ot;
      --maxn;
   }
  printf("\n");

}

Edited by author 17.06.2011 01:42

try this test:
2
1 2

i know the anwer for test #11 is 2.
GOOD LUCK!!!

Sorry for my impudence but my AC program has O(N^2*ln(N)) and takes 234 ms with GREAT optimization (and with memory too). Your solutions (by velocity characteristics) has O(N^2) difficulty and O(N) memory.

First, we should watch all differences between elements (O(N^2)) and then find greatest sequence (O(ln(N))). In process of finding such sequence we should know all differences (O(N^2) memory).

Am I mistaken in something? Could you tell me, in what destination I should think to get quick solution.

Anybody, can tell me what the test 9?

My solution cannot pass test 46. Tell me, please, what special in this test?

I have TLE#12 on C++ and TLE#10 on Pascal but my solution O(N^2*logN)
Please help me.give me any test with TLE.

Edited by author 11.03.2007 11:45

I have WA#3ю Please give me test

I got TL on test 9.

Who can give me some tests(include#5) or hints?

My program have WA #9 and I can not find mistake. Who know some complex tests, please, give me tests that I find mistake in my code.