Hi everyone, I'm trying to solve this well-known problem, but with ternary search. I think it's possible, and in fact all the test cases I've proved pass, but I keep getting WA, so it might be some problems. If some one could help me, or tell me why this approch doesn't work. Here's my code:
#include <bits/stdc++.h>
#define EPS 1e-9
using namespace std;
double l, w;
double f (double x) {
return x*(l-x-x)*(w-x-x);
}
double ternary_search () {
double lo = EPS, hi = (((l<w)?l:w)/2.0)-EPS, mid1, mid2;
for (int i=0; i<100; i++) {
mid1 = lo + (hi-lo)/3.0;
mid2 = hi — (hi-lo)/3.0;
if (f(mid1) > f(mid2)) {
hi = mid2;
} else if (f(mid1) < f(mid2)) {
lo = mid1;
} else {
hi = mid2;
lo = mid1;
}
}
return hi;
}
int main () {
while (scanf("%lf %lf", &l, &w) != EOF) {
printf("%.03lf 0.000 %.03lf\n", ternary_search()+EPS, (((l<w)?l:w)/2.0)+EPS);
}
return 0;
}
Thanks!
you have to minimize x(l-2x)(w-2x). The minimum value of this function is definitely Zero. Now we can make it zero in two ways. if we set x=0 then the function becomes zero. Also we can make zero l-2x=0 and w-2x=0 but neither l and w can be negative. therefore, only min(l,w)-2x can be zero. that means x=min(l,w)/2. No need to do ternary search for the min points. one is 0 another is min(l,w)/2 . Find max value by ternary search and min values in this way. Hope it helps to get AC! have fun :)
Hi,
Your approach looks good in general, but I think it's producing wrong answers because of precision issues.
Notice that this problem:
Given that the
double
type can store correctly about 15–17 significant digits (see here) and considering the propagation errors, it becomes clear why this type of problems arise.I'd suggest a couple of changes to your code:
long double
.Good luck :).
you can solve the problem without ternary search.....
for maximum x----> we have to find the critical point of the following function:
f(x) = (l-2x) * (w-2*x)*x we can write : f(x) = 4x^3-2(w+l)x^2 + wlx
now find the first derivative :
f1(x) = 12x^2-4*(w+l)x + wl
now to find the critical point :
f1(x) = 0
=> 12x^2-4*(w+l)x + wl = 0
Let,
a = 12
b = -4(w+l)
c = wl
so x = (-b-sqrt(b*b-4*a*c))/2*a
now for minimum :
we know minimum value is 0.
we can make f(x) = 0 by selecting x = 0 and x = min(l,w)/2.