Sad_reacts_only's blog

Query regarding time complexity of the solution

By Sad_reacts_only, history, 4 years ago, In English

I have made a submission to problem — 1398G - Соревнования по бегу My submission — 90009972

According to me, it's time complexity is O(n^2 / 32) and n is 2*10^5. Then why it's not TLE? or am I calculating the time complexity wrong?

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

The code you wrote is in fact $$$O(\frac{n^{2}}{32})$$$ but apparently the operations that are being made are simple enough for compiler to somehow optimise them. I've tried to submit the same code without pragmas and it got TLE so yeah, it's a matter of compiler optimisation. Similar thing happend in the very same contest, some people submitted brute force solution in $$$O(n^{2})$$$ $$$n \leq 10^5$$$ for problem C and got accepted despite many hacking attempts.

→ Reply
»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I don't understand the code but I'm going to point out a very strange behaviour.

Zadymiarz12345 used C++17 to run the code. Sad_reacts_only used C++14 to run the code. I was a bit curious so I ran the code several times and observed that C++11 and C++17 gave TLE every time but C++14 gives AC every single time. Isn't this strange considering that C++17 is supposed to be faster than C++14?

→ Reply