ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1318. Logarithm

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 (-)
Posted by Dmitry 'Diman_YES' Kovalioff 17 Apr 2004 12:43
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 (-)
Posted by Sergey Chernykh 24 Aug 2004 22:49
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 (-)
Posted by Fat Peter 24 Sep 2004 20:18
Can you tell me more about it?I got TLE...:(
Re: Re: Ultra-strict optimization (-)
Posted by Sergey Chernykh 18 Oct 2004 16:30
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.