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

Taking more execution time than expected
Автор errorfound, история, 3 года назад, По-английски

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?

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

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

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

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

    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.

    → Ответить
»
3 года назад, # |
← Rev. 5   Проголосовать: нравится +3 Проголосовать: не нравится

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

→ Ответить