I have an O(n^2) algorithm and n<=10^4. Will it pass the servers or will it give TLE?
Depends on Time Limit .
What do you think is this agains the rules?
You cannot share the run-time or space complexity of your solution
I’m not really 100% sure…
Did I say which question was I referring to? Did I even say anything remotely related to a XYZ solution to a ABC question? I am just overall curious about the speed of the codechef servers.
I also wanted to know whether an O(n^3) would pass for n<=10^3.
@asif_mak say it is 1 second? Will it pass? And if it is 2 seconds? Just curious.
Just try it out
The estimation you can use is, that computer can do about 1 billion operations in 1 second. But thats just rough estimation.
You may have idea of time using this table also , the data is for N =100
Approximate completion time for algorithms, (source - topcoder)
O(Log(N)) 10^-7 seconds
O(N) 10^-6 seconds
O(N*Log(N)) 10^-5 seconds
O(N^2) 10^-4 seconds
O(N^6) 3 minutes
O(2^N) 10^14 years.
O(N!) 10^142 years.
@ajinkya1p3 I don’t want to waste my time coding a solution that is bound to give me TLE. Rather that time will be well spent thinking a better solution :). But I guess there is no other way.
Hope for weak test cases and it will pass…
I think you would know it better than me @betlista that Codechef doesn’t give you an AC so easily. Weak tests are rare, that’s what makes Codechef good.
he might want to say that log N takes 10^(-7) seconds for N=100.
10^-7 seconds i mean ,
see it here , please donot downvote as it decreases my karma or reputation without any reason.
Wow, very bad formatting also on TopCoder page…