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.
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.
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.
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.
Well, if its codechef you can just put in random values until it passes :3 . 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-
Author takes 5 hrs to code and contest is of 2 hours
Authors code passes in 2.99 sec and Time limit is 3 sec
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 . 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)).
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