Elhabashy's blog

time complexity
By Elhabashy, history, 5 years ago, In English

hello everyone , why my submission in this problem accepted ? the time complexity of code in worst case is (10 ^ 12 ) , There are 17 attempts to hack my code but all are falid

the problem : 1238A - Prime Subtraction

my submission : 62130511

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

»
5 years ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it

GNU C++ compiler is very smart :)

When it tried to compile your code, it saw:

1) if n<3, answer is NO.

2) if n>=3, then:

a) if n changed, answer is YES

b) if n hadn't changed, answer is YES too

So, in executable file your function "factorize" is never used.

How to see it?

At first, if you will write cout<<n<<endl in "factorize" function, your solution will immediately get TL.

At second, there is a site https://godbolt.org which shows you how your code looks like when it is already compiled.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Yep, it is very smart! Sometimes I cannot optimize my code in a complex code(that doesn't access arrays and doesn't do heavy operations). I leave it for the compiler to do its final job! ;)

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +8 Vote: I do not like it

    thank you for explain this Wind_Eagle

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

I am not sure but I feel this is due to O2 optimization. I have tried your code on my local compiler and easily found a testcase that times it out. Codeforces uses very optimizing flags for best performance especially unroll loops which I feel is the reason for your fast code execution. You are not accessing any array which even fastens the code. All you are doing is simple operations and not heavy ones(except for the modulo in while loop which you don't check on a lot).

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    If I'm not mistaken this happens without -O2 too.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I guess. But somehow, it doesn't work with my local compiler. I have C++11 default flags on. I am not sure why it doesn't work. If you have a method to enable such on my local compiler, can you tell me it?

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thank you for help

    Ahmadsm2005

    → Reply