sobo's blog

By sobo, history, 6 weeks ago, In English

Hi,

I understand that the rule of thumb for 1sec per test case execution to keep the number of operation upto 5*10^8. In some platforms like tocoders, I guess it is 10*10^8. However, I feel it sheerly depends on what kind of operations we are doing.

But after doing some digging, I found that 1sec/testcase and 2sec/test case is merely same. I have a problem where the input array size is 10^5 and the number of queries can run upto 10^5 as well. So for each query if my complexity is O(n) and for all the queries, essentially the number of operations can be upto 10^10. Which should naturally take more than 1 sec and hence the test case won't run in 1 sec. But I have given 2 sec.

So my question is that can anyone please explain me that why it can't even run in 2 sec as well? I am a beginner and hence please excuse me if I am asking something stupid or obvious.

Thanks.

 
 
 
 
  • Vote: I like it
  • -15
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sobo (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it +24 Vote: I do not like it

If we can do 10^5 in 1 sec, then in y seconds, we can do y*(10^5) operations. Not (10^(5*y).

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
»
6 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

2 sec limit gives you liberty to use functions like lower_bound,map.find,set.erase etc, as the are performed in O(log n). So your code complexity can be O(n*log n) but not O(n^2).