Anyone please explain me this article, binary search extended.

While following the competitive programming playlist I just came across this article.

Below described is my exact point, please explain me this.

I feel very strongly that the example given in the above text is not appropriate, how we narrowed down our search space from 1....10**6 to 1 to 1000. Should be explained in more details.

The example is based on problem to find the square root of the number. Since the number can be between 1 to 10^6, the square root would obviously be between 1 to 10^3.

Cheers :slight_smile:

1 Like

you find it from the problem statement, and if you can’t just put 1e18 as upper bound.

1 Like

@c0d3_k1ra

In this case it seems obvious, but while solving it for any variable no. you will need to have some formula through which you can say square rot for 10^6 will be between 1 to 1000. So I am asking how we will find this range.

One of the best thing I saw today. XD. Practically correct, 10/10.

Not always @vijju123

I myself got TLE in a recent CF round, due to choosing upper-bound of binary search to 1e18, while same solution with upper bound 1e6 gave AC.

Wherever you can accurately determine upper-bound (and lower-bound too), the better. Otherwise 1e18 is always there as a last resort.

For Example, in problem L56AVG L56AVG Problem - CodeChef , you can set upper-bound as max(A) and lower-bound min(A), as we know from formula of average that average always lie between min and max.

In an algorithm of complexity $Log_2

N$ , I really dont expect that ${10}^{18}$ will get TLE. I think C++ will pass with that bound- CF does not give any time multipliers like JAVA, so that may be the reason.

But the thing i wanted to convey is, that having stricter bounds always helps.

Maybe in the question, your solution have higher complexity, TL might be too strict, anything can happen.

Well, if its codechef you can just put in random values until it passes :3 :stuck_out_tongue: . At CF, I really dont expect such instances. If this happens for a C++ solution, and really the TL is set tooo strict (as in setter’s sol takes 2.9sec and TL is 3sec), then the CF community will flame that poor guy to his death lol. They already have that word “Tumor” for those problems where-

  1. Author takes 5 hrs to code and contest is of 2 hours :slight_smile:
  2. Authors code passes in 2.99 sec and Time limit is 3 sec :smiley:
  3. The code has 0 logic and concept and is all about 300 lines of implementation.

But yeah, nothing what I say can argue against your point. So thats well taken :slight_smile: . Though I will say that if a difference of Log_2{10}^{18} and Log_2{10}^{6} is mattering, then either the solution isnt correct/good, or the setter and tester have very poorly decided time limit.

Well, in my case, i had accidently used Double.MAX_VALUE, and that made the difference.

Here’s the TLE (first one) and AC (second one) solution of Good Bye 2017 of CF. Only difference being the bound of binary search. Both have time complexity O(N*log(BS_RANGE)).

Though i get the idea, i haven’t yet seen such instances of “flaming that guy to death” on CF. :stuck_out_tongue:

@taran_1407 - Double.MAX_Value gives {10}^{308} , not {10}^{18}…no way such a minor difference is gonna bring your run time from 2 sec to 0.14 XD. Here- Java double.MAX_VALUE? - Stack Overflow . Your solution is a few hundred times slower? :3

BTW, read here- http://codeforces.com/blog/entry/53903

Not flaming to death, but well…XD

I know above i made a mistake (around 10^{308}), but it conveys the thing i wanna tell. :stuck_out_tongue:

No! There is a HUGEEEEE difference in setting upper bound from {10}^{6} to {10}^{18} and {10}^{6} to {10}^{308} . PS: Looks like you got a latex error there :stuck_out_tongue:

Corrected latex error. But the point is, select bounds carefully. :smiley:

My code is the outcome of selection of bounds carelessly.

I will call it “failure of insight” :3 . I mean CMON XD {10}^{308} FFS LOL.

What if it were python? {10}^{7000}?

Disaster strike it would be. :stuck_out_tongue:

Actually in my mind, MAX_VALUE was going around 10^{18} at that time, during the contest.

1 Like