Hi,
I recently coded for CSBUQ, my code has complexity (N + Q) * log N.Now as per problem constaints max value for both N and Q is 5 * 10 ^ 5, for which total no of operations computes to around 2 * 10 ^ 7, I can’nt understand why my code occasionally gives TLE, (failing in worst case some times), and runs absolutely fine other times.
Any explanation why :
1.codechef engine is giving TLE even for 10 ^ 7 operations ( I think it can support 10 ^ 9 ops for time limit of 1 sec).
2.why the code gives TLE occasionally, and runs in time other times.
I don’t know how many operations codechef servers actually support within 1 sec. It is safe to assume that 1e7 operations are performed during 1 sec.
Talking about time complexity, You must have heard about constant factor associated with time complexity. Your code too has high constant factor.
Suppose, you are given a number N and asked to find out how many numbers from 1 to 500 are factor of this number. we run a simple loop and get the count. in 500 iterations.
We run 500 iterations irrespective of input size. But we cannot ignore constant factor, say in same problem, we were given 1e6 numbers instead of 1.
All that changes a code from TLE to AC in these cases is reduction of constant factor associated.