How to avoid TLE?

Posted by

Geworm 17 Apr 2004 08:45

I think O(n^2) algorithms will certainly lead to TLE.

I tried to count how many results will be larger than 10,100,... and got an algorithm, and its complexity is O(800nlogn), still TLE.

I heard that there was an O(n) algorithm, can anyone tell me how to do that? Thanks.

Ultra-strict optimization (-)

Re: Ultra-strict optimization (-)

Posted by

Geworm 19 Apr 2004 09:16

Do you mean optimize the simple O(n^2) solution or use an O(n) algorithm?

Re: Re: Ultra-strict optimization (-)

My ultra-optimized O(n^2) solution using some assembler in critical parts of code passed in 0.718 seconds. But I spend almost 2 hours for optimizing my code.

Re: Re: Ultra-strict optimization (-)

Can you tell me more about it?I got TLE...:(

Re: Re: Ultra-strict optimization (-)

You should use a table, which for every 2^k (0 <= k <= 127) keeps a value of Trunc(log10(2^k)). You should also keep a table with powers of 10 (10^0 .. 10^39). In the main loop of the program (which is straight-forward) you compute B = A[i] XOR A[j], then find the position k of the most significant bit of B (k is counted from zero). k is obtained using assembler instruction BSR (Bit Scan Reverse).

At this point you know that 2^k <= B < 2^(k+1). Now, M := Trunc(log10(2^k)), and N := Trunc(log10(2^(k+1)). If B >= 10^N, then Trunc(log10(B))=N, else Trunc(log10(B))=M.

Starting with this algorithm and optimizing it, you should get AC.