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.

My algo is DP + Binary Search O(N^2*log(N));

I check my program on 1000 random tests and he gives right answer...

What trick in test 3?

Please help who know somthing about #3...

please help me to find bugs in my program, all my test past successfully and I don't know where mistake. My code:

struct num
{
  int data;
  int index;
};

int comp(const void *p1,const void *p2) {
    const num *t1=(const num*)p1, *t2=(const num*)p2;
  if (t1->index==0) return -1;
  else if (t2->index==0) return 1;
    else if (t1->data>t2->data) return 1;
    else if (t2->data>t1->data) return -1;
    else return 0;
};

num a[2001];

int main(int argc, char* argv[])
{
  int n,i,j,r[2001],max,d,t,m,alpha;
  int c[4002];
  cin>>n;
  for (i=1; i<=n; i++)
    {
    cin>>a[i].data;
    a[i].index=i;
    }
  qsort(a,n+1,sizeof(num),&comp); /* quick sort */
  for (i=2; i<=n; i++)
    {
    r[i]=a[i].data-a[i-1].data;
    }
  max=1;
  alpha=0;
  t=-1;
  for (i=n; i>1; i--)
    {
    if (t==r[i]) continue;
    t=r[i];
    if (t==0) continue;
    m=1;
    c[alpha+m]=a[i].index;
    d=0;
    m=2;
    c[alpha+m]=a[i-1].index;
    for (j=i-1; j>1; j--)
      {
      d=d+r[j];
      if (d>t) break;
      else if (d==t)
        {
        m++;
        c[alpha+m]=a[j-1].index;
        d=0;
        };
      }
    if (m>max)
      {
      alpha = (alpha==0) ? 2001 : 0;
      max=m;
      };
    }
    if (max==1)
      {
      cout<<max<<endl;
      cout<<a[1].index<<" ";
      }
    else
      {
      alpha = (alpha==0) ? 2001 : 0;
      cout<<max<<endl;
      for (i=alpha+max; i>alpha; i--)
        {
        cout<<c[i]<<" ";
        }
      }
  return 0;
}

Which complexity is the best? I got ac with O(n^2*logn), but the running time of my program was 0.25s.

[code deleted]

Edited by moderator 10.08.2006 10:07

"Different elements" means "different numbers". I.e. delta of the progression should NOT be equal to zero.