facug91's blog

UVa 10215 — The Largest/Smallest Box
By facug91, 10 years ago, In English

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 &mdash; (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!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi,

Your approach looks good in general, but I think it's producing wrong answers because of precision issues.

Notice that this problem:

  • Requires calculating a value from many operations, each one propagating a certain amount of "error".
  • Involves numbers with a high number of significant digits—the input numbers are in the order of 104 (and that's without considering the possibility of digits after the point) and you end up evaluating a polynomial of degree 3. This means you end up juggling numbers in the order of (104)3 = 1012.

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:

  1. Try using variables of type long double.
  2. Don't set a fixed number of iterations in the ternary search function. Instead, you could do something like:
while (fabsl(lo - hi) > EPS) {
     // do calculations
}

Good luck :).

→ Reply
»
9 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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.

→ Reply