Is my application of binary search not right here?

Question

So, I was solving this problem: http://www.spoj.com/problems/IMMERSED/

A fantastic discovery is about to happen in the biology field, and you are part of the team making the research. The research is about measuring the cells growth in an environment oxygenless and in presence of a toxic substance. The team came to a courious hypothesis, the analyzed data tells them that: the growth, the number of days and the toxicity; are related by this formula:

P = N*N^cN;

where P is the growth measured in thousands of cells.

N is the elapsed number of days.

and c is the constant that relates to the toxicity level of the experiment.

Your biology partners need to takeout some tissues from the cells when these cells reach a specific growth. They require you to write a program that tells them the exact time when this will happen, given a toxicity level and the growth required.

Input

The first line is T (1 ≤ T ≤ 40,000), the number of test cases, then T test cases follow.

Each test case is a line with 2 integers(P c) separated by a space.

P (1 ≤ P ≤ 10¹⁵)

c (1 ≤ c ≤ 5)

Output

For each test case you have to output the expected time in decimal format.

What I did was used binary search for finding the number of days as follows:

#define eps 1e-7
const double cont = 14.0;
double p,c;
double binary (double start, double end);
double func (double n);
int main (void)
{
 int t;
 cin>>t;
 while (t != 0)
 {
 cin>>p>>c;
 double mid,ans,start=0,end=cont;
 ans = binary(start,end);
 cout.precision(6);
 cout<<fixed<<ans<<"\n"; 
 t--;
 }
 return 0;
}
double func (double n)
{
 double ret = n*pow(n,c*n);
 return ret;
}
double binary (double start, double end)
{
 if (start <= end)
 {
 double mid = start + (end-start)/2.0;
 if (func(mid)-p <= eps)
 return mid;
 else if (func(mid)-p > eps)
 return binary(start,mid);
 else
 return binary(mid,end);
 }
}

However, on running my code, it gives incorrect answer on even the given test cases which are:

Input:
3
1 1
3 4
100 1
Output:
1.000000
1.207384
3.086308
My output (for the above input)
0.875
0.875
1.75

PS: I didn't post the libraries and all to avoid cluttering. Also, I will set it to be 6 decimal places once I get the correct value. I just want to know, is my logic incorrect or my binary search has been implemented incorrectly?

Edit: New code I submitted

double binary (double start, double end)
 {
 if (start <= end)
 {
 double mid = start + (end-start)/2.0;
 double delta = func(mid) - p;
 if (delta < -1*eps)
 return binary(mid,end);
 else if (delta > eps)
 return binary(start,mid);
 else
 return mid;
 }
 }

• wimh: This if statement looks suspicious; if (func(mid)-p <= eps). If they can be equal, you must test that in a different way. Also I don't understand the reason of the last else.
• Megha: Your mid is totally dependent on start and end values and that is what you are returning. How do u expect it to be 1 given the fact that you are starting from 1 to 14 and than dividing it into halves...so 0--14, 0 to 7, 0 to 3.5 , 0 to 1.75... 0 to .875 ..Are you sure mid is what you want?
• hans: @Meghaa, but in binary search, we always find out the mid value and compare it with that. Should it be different in this case?
• Megha: well i think its not about binary search...its about what you are expecting your code to do...do u wish to find out the day at which a certain calculation was less than an expected value?
• IVlad: If I submit your code as C++ (g++ 5.1) code, I get Wrong Answer. Can you please post the exact code you're submitting and how?

Answer 1

You are testing in an unsound sequence:

if (func(mid)-p <= eps)
 return mid;
else if (func(mid)-p > eps)
 return binary(start,mid);
else
 return binary(mid,end);

Try

if (func(mid)-p < -eps)
 return binary(mid,end);
else if (func(mid)-p > eps)
 return binary(start,mid);
else
 return mid;

I'm also not sure of the two recursive calls. I kept your logic for which is called in which case (because I might have misunderstood your formula) but they look backwards to me.

What I'm sure of is that you should test for (and use a recursive calls for) the two outside cases (func(mid)-p < -eps and func(mid)-p > eps) before the inside case (which is then effectively abs(func(mid)-p) < eps)

Edit: The cleaner (faster) version of that binary search is:

double binary (double start, double end)
{
 for (;;)
 {
 double mid = (start + end) * .5;
 double delta=func(mid)-p;
 if ( delta < -eps)
 start = mid;
 else if (delta > eps)
 end = mid;
 else
 return mid;
 }
}

A Newton search is likely faster than that.

• hans: Well, this works but now, with this logic, the problem gives Time Limit Exceeded. I don't know if we can do better than binary search. Can we?
• IVlad: @hans online judge compilers might not use optimizations. Try storing the value of func(mid) in a variable and using that variable in your if and else if.
• JSF: Trivially you can get faster by computing and storing func(mid) once per step instead of twice. You can also make it faster using a loop instead of recursion. (Though an optimized build ought to do that for you in the obvious case of tail recursion). For most well behaved functions, a Newton search works better than binary, but you need some calculus skill (or a visit to wolframalpha.com to code that).
• JSF: wolframalpha gave (dP(C, N))/(dN) = N^(C*N)*(1+C*N*(1+log(N))) as the answer to the calculus question that you would need in order to code a Newton search. You still would need to know what a Newton search is.
• JSF: @Mpeti, I was wrong in my reply to you. I had only tested the cases hans gave. Over the full range, there is a much better reason to follow your suggestion (and that might be the major remaining problem). When P is very large, func(N) can't be computed accurately enough using the double type, so the loop never stops, even though mid is the correct value for N

Answer 2

Beside the problem with the search JSF explained, you're also calculating way more accurately than you need to.

You need N with an accuracy of 10^-6. With your implementation, you're searching until you find the value where you have P with an accuracy of 10^-7. Since the function is exponential and therefore very steep, i.e. P changes very quickly with N, that's going to result in much more computation than necessary.

Instead, you should have a stopping condition end - start < 1e-6.

Now here I have a semantic issue: Does an accuracy of 10^-6 mean that all the digits have to be correct, or is the last one allowed to be off by 1? If it's allowed, either start or end will be a good answer after stopping. If not, you could round them upwards to the nearest 10^-6. You should round up because the statement is probably asking for the first N where func(N) > P, not an approximation for equality. Then if those are different, check if the rounded value of start satisfies the statement. If yes, output that, if not, output the rounded value of end.

Given the upper bound of 14.0, the search space is just 14.0 / 1e-6 = 1.4 * 10^8 elements. The base 2 log of that is just over 27, so you should only need 28 iterations for each test case (maybe 27 if you calculate a more accurate upper bound). This definitely shouldn't require complicated optimizations to pass.

• hans: that doesn't really help to remove the TLE though. :/
• JSF: @hans, post the version you used when you tried MPeti's suggestion. Maybe you misunderstood that suggestion and did not properly deal with the case of P very large. Also test the case of P very large before submitting your proposed solution.