How can I improve memory usage in this code?

#include "bits/stdc++.h"

using namespace std;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    short n;
    cin >> n;

    vector<pair<int,short>> s(n, pair<int,int>());

    for (int i = 0; i < n; i ++) {
        cin >> s[i].first;
        s[i].second = i;
    }

    sort(begin(s),end(s));
    for (short i = 1; i < n; i ++) {
        if (s[i].first == s[i - 1].first) {
            s.erase(begin(s) + i);
            n --;
            i --;
        }
    }

    vector<vector<short>> dp(n + 1, vector<short>(n + 1, 0));

    for (short i = 1; i < n - 1; i ++) {
        short l = i - 1;
        short r = i + 1;
        while (0 <= l && r < n) {
            int dfl = s[i].first - s[l].first;
            int dfr = s[r].first - s[i].first;
            if (dfl == dfr) {
                dp[i][r] = dp[l][i] + 1;
                l --;
                r ++;
            } else if (dfl > dfr) {
                r ++;
            } else {
                l --;
            }
        }
    }

    if (1 == n) {
        cout << "1\n1\n";
    } else {
        short mx = -1;
        short di = 0;
        short dj = 0;

        for (int i = 0; i < n - 1; i ++) {
            for (int j = i + 1; j < n; j ++) {
                if (dp[i][j] >= mx) {
                    mx = dp[i][j];
                    di = i;
                    dj = j;
                }
            }
        }

        int df = s[dj].first - s[di].first;

        mx += 2;

        cout << mx << '\n';

        for (; -1 < di;) {
            cout << s[dj].second + 1 << ' ';
            dj = di;
            di = -1;
            for (short i = 0; i < dj; i ++) {
                if (s[dj].first - s[i].first == df) {
                    di = i;
                    break;
                }
            }
        }

        cout << s[dj].second + 1 << '\n';
    }
}

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;
}

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?

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?

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).

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

Can anybody suggest me the 6th test case?

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

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

test #1
6
7 0 0 0 0 0

my program output "2\n1 2" but gets WA#1

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.

Ьудем рассматривать все возможные разности (в виде 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)

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

I have WA#3ю Please give me test

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

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

try this test:
2
1 2

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

Anybody, can tell me what the test 9?

Why WA 8? Please help me ! I tested my programm many times, but did'not find a mistake. Maybe someone tell me where is wrong or give me same test.
Sorry for my bad english.

Here is my code:
program Project2;

{$APPTYPE CONSOLE}
uses windows;
type din=array of longint;
type IntMas=array[1..2000] of longint;
var mas,mas2:din;
    pre,rez:intMas;
    n,i,dlin,dlin2,kol,u,y,save,KOLM,a,b,sr,MAX,num,del,l,r:longint;
    f:text;
   // lMas:array[1..2000,1..2000] of longint;
   DELTA:array[0..1000000000] of boolean;
    T:BOOLEAN;
    t1,t2,t3,t4:_SYSTEMTIME;



procedure sort(var d,d2:din;var l:longint);
var dlin,dlin2:longint;
     mas2,mas3,Dmas2,Dmas3:din;
begin
t:=false;


dlin:=l div 2;
dlin2:=l-dlin;
setlength(mas2,dlin+1);
setlength(Dmas2,dlin+1);
for i:=1 to dlin do
  mas2[i]:=d[i];
for i:=1 to dlin do
  Dmas2[i]:=d2[i];

setlength(mas3,dlin2+1);
setlength(Dmas3,dlin2+1);
for i:=1 to dlin2 do
  mas3[i]:=d[i+dlin];
for i:=1 to dlin2 do
  Dmas3[i]:=d2[i+dlin];

if dlin>1 then
  begin
  sort(mas2,Dmas2,dlin);
  end;

if dlin2>1 then
  begin
  sort(mas3,Dmas3,dlin2);
  end;
kol:=0;
i:=1;
u:=1;
L:=dlin+dlin2;
while kol<l do
  begin

  if mas2[i]<mas3[u] then
    begin
    inc(kol);
    d[kol]:=mas2[i];
    d2[kol]:=Dmas2[i];
    if i+1<=dlin then
      inc(i)
    else
      begin
      for y:=u to dlin2 do
        begin
        d[kol+y-u+1]:=mas3[y];
        d2[kol+y-u+1]:=Dmas3[y];

        end;
      break;
      end;
    end
  else
    begin
    inc(kol);
    d[kol]:=mas3[u];
    d2[kol]:=Dmas3[u];
    if u+1<=dlin2 then
      inc(u)
    else
      begin
      for y:=i to dlin do
        begin
        d[kol+y-i+1]:=mas2[y];
        d2[kol+y-i+1]:=Dmas2[y];
        end;
      break;
      end;
    end
  end;

//sort()
end;

begin
{assign(f,'input.txt');
reset(f);}
readln({f,}n);



setlength(mas,n+1);
setlength(mas2,n+1);
for i:=1 to n do
  begin
  read({f,}mas[i]);
  mas2[i]:=i;
  end;

t:=false;
if n>1 then
sort(mas,mas2,n);

rez[1]:=1;
kolM:=1;
DELTA[0]:=true;

for i:=1 to n do
  for u:=i+1 to n do
    if not DELTA[mas[u]-mas[i]] then
      begin
      del:=mas[u]-mas[i];
      DELTA[del]:=true;
      num:=mas[u];
      num:=num+del;

      kol:=2;
      pre[1]:=mas2[u];
      pre[2]:=mas2[i];
      l:=u;
      r:=n;
      while true do
        begin
        if mas[l]=num then
          begin

          inc(kol);
          pre[kol]:=mas2[l];
          num:=num+del;
          l:=l;
          r:=n;
       //   break;
          end;

        if mas[r]=num then
          begin

          inc(kol);
          pre[kol]:=mas2[r];
          num:=num+del;
          l:=r;
          r:=n;
         // break;
          end;
        if (mas[r]<>num) and(mas[l]<>num) then
          begin
          if ((abs(r-l)=1) or (abs(r-l)=0))   then
            begin
            if kol>kolM then
              begin
              for l:=1 to kol do
                rez[l]:=pre[l];
              kolm:=kol;
              end;
            break;
            end;
          if mas[(l+r)div 2]<num then
            l:=(l+r)div 2
          else
            r:=(l+r)div 2;
          end;



        end;

      end;


writeln(kolM);
for i:=1 to kolM do
  begin
  write(rez[i]);
  write(' ');

  end;
  //readln;

end.