You are not logged in. Please login at www.codechef.com to post your questions!

×

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.

asked 02 Feb '18, 08:26

arpit728's gravatar image

1★arpit728
6831765
accept rate: 10%


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 :)

link

answered 02 Feb '18, 14:45

c0d3_k1ra's gravatar image

2★c0d3_k1ra
175118
accept rate: 11%

@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.

(02 Feb '18, 23:17) arpit7281★

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

link

answered 03 Feb '18, 04:05

we7d's gravatar image

2★we7d
222
accept rate: 0%

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

(03 Feb '18, 10:15) vijju123 ♦♦5★

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.

(03 Feb '18, 18:57) taran_14076★

For Example, in problem L56AVG https://www.codechef.com/problems/L56AVG , 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.

(03 Feb '18, 18:59) taran_14076★

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.

(03 Feb '18, 19:40) vijju123 ♦♦5★

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.

(03 Feb '18, 19:53) taran_14076★

Well, if its codechef you can just put in random values until it passes :3 :p . 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 :)
  2. Authors code passes in 2.99 sec and Time limit is 3 sec :D
  3. The code has 0 logic and concept and is all about 300 lines of implementation.
(03 Feb '18, 20:52) vijju123 ♦♦5★

But yeah, nothing what I say can argue against your point. So thats well taken :) . 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.

(03 Feb '18, 20:52) vijju123 ♦♦5★

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)).

http://codeforces.com/contest/908/submission/33783244

http://codeforces.com/contest/908/submission/33792945

(03 Feb '18, 21:27) taran_14076★

Though i get the idea, i haven't yet seen such instances of "flaming that guy to death" on CF. :P

(03 Feb '18, 21:28) taran_14076★

@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- https://stackoverflow.com/questions/16146219/java-double-max-value . 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

(03 Feb '18, 21:44) vijju123 ♦♦5★

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

(03 Feb '18, 22:47) taran_14076★

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 :p

(03 Feb '18, 23:13) vijju123 ♦♦5★

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

My code is the outcome of selection of bounds carelessly.

(03 Feb '18, 23:34) taran_14076★

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

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

(03 Feb '18, 23:39) vijju123 ♦♦5★
1

Disaster strike it would be. :P

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

(03 Feb '18, 23:52) taran_14076★
showing 5 of 15 show all
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,658
×1,041

question asked: 02 Feb '18, 08:26

question was seen: 376 times

last updated: 03 Feb '18, 23:53