errorfound's blog

Taking more execution time than expected
By errorfound, history, 4 years ago, In English

In Problem D-Bandit in a City (Codeforces Round 678), the binary search solution has complexity of O(Nlog(2e14)), where N=2e5, So, it should take around 100ms, but most of submissions using binary search, like this are taking more than 900ms. Can anyone tell why is this happening?

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

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

Probably significant amount of this time is input
I don't know expected performance of cin with magic incantations, but there are 400000 values to be read

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

    If input is the problem, then the intended linear solution would also have taken large time.
    Even taking 1e6 values will take no more than 50ms.

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

2e5 * log(1e14) = 1e7

Also there is a really big constant in front of it. There are lots of operations and there is recursion
Also there are lots of random jumps that may make processor caching ineffective
Also there is a huge input
I believe it is a combination of all those factors

→ Reply