ikbal's blog

why this code gets TLE? Problem is COCI 2012-2013 contest 6 jedan.
By ikbal, 12 years ago, In English

N<=10^4

//includes

using namespace std;

template inline T abs ( T a ){return a>0? a : -a;}

typedef pair<int,int> ii;

typedef long long Lint;

const int MAXN = 1e4+100;

const int inf = 1e9+5;

const Lint mod = 1e9+7;

int N;

int ar[MAXN];

Lint dn[2][MAXN];

void add(Lint &a,Lint b){ b%=mod; a = (a+b)%mod; if(a<0) a+=mod; }

int main(){

//~ freopen("f.in","r",stdin);
//~ freopen("f.out","w",stdout);

cin >> N ; 

For(i,1,N) scanf(" %d",ar+i);

if(ar[N]!=0 && ar[N]!=-1) return cout << 0 << endl, 0 ;
if(ar[N]==-1) ar[N]=0;

if(ar[1]!=0 && ar[1]!=-1) return cout << 0 << endl, 0 ;
if(ar[1]==-1) ar[1]=0;

dn[N&1][0] = 1LL;

for(int i=N-1;i>0;i--){

    memset(dn[i&1],0,sizeof dn[i&1]);

    if(ar[i]==-1){

        Rep(k,0,MAXN){
            if(k>0) add(dn[i&1][k],dn[(i+1)&1][k-1]);
            add(dn[i&1][k],dn[(i+1)&1][k]);
            if(k<MAXN) add(dn[i&1][k],dn[(i+1)&1][k+1]);
        }

    }else{

        int k = ar[i];

        if(k>0) add(dn[i&1][k],dn[(i+1)&1][k-1]);
        add(dn[i&1][k],dn[(i+1)&1][k]);
        if(k<MAXN) add(dn[i&1][k],dn[(i+1)&1][k+1]);

    }

}

cout << dn[1][0] << endl;

return 0;

}

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

First, one can notice that the maximal possible height is 5000. This observation will speed up your solution twice. Also it's better not to use long long when it isn't necessary. The last thing is to make your function add inline. And the main step: you don't need to use the % operation in this problem at all. Just subtract mod every time the number exceeds it. With these four optimizations my code works 0.3s on the maxtest.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    thanks

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      In the first edit of my previous comment I forgot the main thing: never use the % operation in such problems!

      → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Actually, I use long longs and modulos like a lunatic, and still get 0.4 seconds on the largest test case :D EDIT: after an optimization (not affecting modulos or long longs), it's 0.2s. Here.

    Even the optimalization of max. height 5000 is sufficient to get rid of TLEs (around 0.7s on the largest test case). The remaining optimizations are quite insignificant in comparison.

    → Reply