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

Why does this binary search show TLE ? Problem D: Educational Codeforces Round 53 (Rated for Div. 2)
Автор watchdogs132, история, 6 лет назад, По-английски

Here is the link to the problem :http://mirror.codeforces.com/contest/1073/problem/D

Here is the link to my submission : http://mirror.codeforces.com/contest/1073/submission/44895822

It shows TLE on test case #8.

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It seems that you increment 'c' by 1 for every candy you buy. As the solution can be 1018, you will not finish a calc(mid) invocation in time when mid is large.

Also, 'high' starts at 3e10, and you look for a solution in [low, high]. But the solution can be way larger than that.

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

while(temp>=*min_element(v.begin(),v.end()) That check works in O(N) every time, what leads to TL. Probably you should save *min_element in some variable to avoid that.

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

    Yes, it works for the test#8 though , but I get TLE on test#9(Link: https://mirror.codeforces.com/contest/1073/submission/44903513 ). Thanks anyways. On a side note , do you think my code can be optimized more to get it accepted ? or do I need to change my approach entirely?

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

      I'd suggest storing values that are less or equal than T in a set. That way you won't be spending time considering bigger elements. But, I'm still not sure if that will get AC. Probably you should give up binsearch and think of another idea.

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

      The binary search part is unnecessary: 44923323

      In a case like

      200000 1000000000000000000
1 1 1 1 1 1 1 ...

      Your calc function runs in O(T) time.

      → Ответить