Can anyone tell me why I am getting TLE in
http://www.codechef.com/viewsolution/4855478
?
-
In your code, ‘b’ represents ‘A’ as
mentioned in the problem. A < 10^9. -
And your solution has the loop
while(k–){}. Hence your solution
will take approximately A steps, or
in easier way, the number of steps of
your problem is of the order A. Hence
your code is an O(A) solution. For
algorithm analysis:
http://www.geeksforgeeks.org/analysis-of-algorithms-set-1-asymptotic-analysis/ -
Now, we all know the computation
power of a processor is also limited.
Assume 1 sec ~ 10^8 operations per
second . (for SPOJ old server it
is 4*10^6). Keep this in mind while
solving any problem. -
So if A < 10^6 then your solution
will pass, but here A<10^9, hence it
is giving ‘Time Limit Exceeded’. Try
to come with a optimal solution
-
Hint: This problem has a O(k) solution and k, according to problem statement is < 100
2 Likes