Discussion @ 1090. In the Army Now @ Timus Online Judge

Bobur TLE#4 with my code, help!! [7] // Problem 1090. In the Army Now 17 Feb 2008 12:24

var
   i, j, q, key, n, k, k1, max, row : integer;
   a : array [1..10000] of integer;

begin
read(n, k); row := 1; max := 0;
for k1 := 1 to k do
    begin
for i := 1 to n do
read(a[i]);
q := 0;
For j:=2 to n do
Begin
   Key:=a[j];
   I:=j-1;
   While (i>0) and (A[i]>key) do
       Begin
           A[i+1]:=a[i];   inc(q);
           Dec(i);
       End;
   A[i+1]:=key;
End;
if max < q then begin max := q; row := k1; end;
end;
writeLn(row);
end.

Bobur Re: TLE#4 with my code, help!! [5] // Problem 1090. In the Army Now 23 Feb 2008 19:09

here another code but yet TLE#4!!

   var
   b : array [1..10000] of smallint;
   j, n, k, x : smallint;
   max, s : integer;
   i, m, q : byte;

begin
   read(n, m);     q := 1; max := 0;
   for i := 1 to m do
     begin
       s := 0;
       for j := 1 to n do
         begin
           read(x);
           b[x] := j;
         end;
       for j := 1 to n do
         begin
           s := s + b[j] - j; x := b[j];
           for k := b[j] downto j + 1 do
           b[k] := b[k-1];
           b[j] := x;
         end;
       if max < s then begin max := s; q := i;   end;
     end;
   writeLn(q);
end.

Fetisov Alex [USTU Frogs] Re: TLE#4 with my code, help!! [4] // Problem 1090. In the Army Now 24 Feb 2008 01:31

You should have nearly O(k*n*logn) (mayby O(k*n*sqrt(n)) algo to avoid TLE . What's about yours?

Bobur Re: TLE#4 with my code, help!! [2] // Problem 1090. In the Army Now 5 Mar 2008 17:03

i don't understand you, pls ubderstand and give me some hints

Bobur i find new algo, but yet TLE#4!!! [1] // Problem 1090. In the Army Now 14 Mar 2008 20:39

   var
   a, b, c : array [1..10000] of smallint;
   j, n, k : smallint;
   max, s : integer;
   i, m, q : byte;

begin
   read(n, m);     q := 1; max := 0;
   for i := 1 to m do
     begin
       s := 0;
       for j := 1 to n do
         begin
           read(a[j]);
           b[a[j]] := j;
           c[j] := 0;
         end;
       for j := 1 to n-1 do
         begin
           s := s + b[j] - j+c[j];
           for k := a[b[j]] to b[j]-1 do
           inc(c[k]);
         end;
       if max < s then begin max := s; q := i;   end;
     end;
   writeLn(q);
end.

Slam [Tartu U] Re: i find new algo, but yet TLE#4!!! // Problem 1090. In the Army Now 21 Mar 2008 17:38

use mergesort

googled Re: TLE#4 with my code, help!! // Problem 1090. In the Army Now 28 Oct 2008 15:08

Hey, I got TLE on this code with O(k*n*lgn) using Indexed trees. My code is attached for reference:

#include<iostream>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
int bit[10001];
bool myfunc(vector<int> a,vector<int> b)
{
if(a[0]>b[0])
return true;
return false;
}
void update(int x,int n)
{
     int i;
     for(i=x;i<=n;i+=i&-i)
     bit[i]++;
}
int getval(int x)
{
int i,ans=0;
for(i=x;i>0;i-=i&-i)
ans=ans+bit[i];
return ans;
}
main()
{
      int n,k,ans=0,ind;
      scanf("%d %d",&n,&k);
      int cas=1;
      while(k--)
      {
       int i;

       vector<vector<int> > arr;
       vector<int> emp;
       arr.clear();
       for(i=0;i<n;i++)
       {
        arr.push_back(emp);
        arr[i].push_back(0);
        scanf("%d",&arr[i][0]);
        arr[i].push_back(i+1);

       }
       sort(arr.begin(),arr.end(),myfunc);
       memset(&bit,0,sizeof(bit));
//       cout<<bit[1]<<endl;
       int val=0;
       for(i=0;i<n;i++)
       {
//        cout<<arr[i][1]<<" ";
//cout<<val<<" ";
        val=val+getval(arr[i][1]);
        update(arr[i][1],n);

       }
//       cout<<endl;

       if(ans<val)
       {ans=val;ind=cas;}
       cas++;
      }
      printf("%d",ind);
//      cin>>ind;
}

Any hints?

Liu Strong Re: TLE#4 with my code, help!! // Problem 1090. In the Army Now 4 Apr 2008 21:39

This is not an A+B problem and you should use a more efficient algorithm to avoid using a lot of time.

Discussion of Problem 1090. In the Army Now