watchdogs132's blog

Why does this binary search show TLE ? Problem D: Educational Codeforces Round 53 (Rated for Div. 2)
By watchdogs132, history, 6 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

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

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.

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

    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?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

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

      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.

      → Reply