watchdogs132's blog

Why does this binary search show TLE ? Problem D: Educational Codeforces Round 53 (Rated for Div. 2)
By watchdogs132, history, 7 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

»
7 years ago, hide # |
 
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
»
7 years ago, hide # |
 
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