Блог пользователя Sad_reacts_only

Query regarding time complexity of the solution

Автор Sad_reacts_only, история, 4 года назад, По-английски

I have made a submission to problem — 1398G - Running Competition 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?

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
4 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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?

→ Ответить