TopCoder problem "LocalMax" used in TCCC05 Finals (Division I Level Three)



Problem Statement

    We want to find the location of a local maximum in an unknown function. y = f(x) is a continuous real-valued function defined on the real numbers. We already have a number of data pairs, (xi, yi), and we need to find a small interval on the x axis that is guaranteed to contain at least one local (or global) maximum. But taking a sample from this function is quite expensive so we are only allowed to take N samples. Our problem is to choose them in such a way as to minimize the size of the interval that we determine.

The sampling will be done sequentially: we choose a value of x and find the corresponding y value, f(x). We repeat this process N times, choosing the x value based on all the data collected so far. We are willing to assume that no two y values will be exactly equal to each other.

Create a class LocalMax that contains a method length that is given N, the number of samples we can take, and double[]s xData and yData (the existing data pairs). It will return the worst case length for our interval around a local maximum using optimal sampling. If it is not possible to make such a guarantee, it returns -1.0.

 

Definition

    
Class:LocalMax
Method:length
Parameters:int, double[], double[]
Returns:double
Method signature:double length(int N, double[] xData, double[] yData)
(be sure your method is public)
    
 

Notes

-The returned value must be accurate to within a relative or absolute value of 1E-9
 

Constraints

-N will be between 0 and 25 inclusive.
-xData will contain between 1 and 50 elements inclulsive.
-yData will contain the same number of elements as xData.
-The elements of yData will be distinct.
-The elements of xData will be distinct.
-Each element of xData and yData will be greater than 0.0 and less than 10000.0.
 

Examples

0)
    
1
{3,4,5}
{3,4,5}
Returns: -1.0
From the data we already have we cannot guarantee that this function even has a local maximum -- it might be monotonically increasing.
1)
    
0
{3,4,5}
{3,5,4} 
Returns: 2.0
We know that there is a local maximum between x=3 and x=5.
2)
    
2
{3,5,8}
{35,923.2,17}  
Returns: 2.0
Here is one way (there are others) get an interval of length 2 or less with just two additional samples. Take the first sample at x=6.5. The worst case is that the corresponding y value is less than 923.2. In that case we know that the interval (3,6.5) contains a local maximum, and that the y value at x=5 is greater than either endpoint y value. Take the second sample at x=4.7. In the worst case the corresponding value of y will be bigger than 923.2, in which case we could conclude that there is a local max somewhere in the interval (3,5).
3)
    
1
{3,4,6,5}
{32,53,68,47}
Returns: 1.0
If we take a sample at x=4.0+epsilon, for some tiny epsilon, then the worst case would be that the corresponding y value would be smaller than 53. In that case the interval between 3.0 and 4.0+epsilon would contain a local maximum. So by choosing epsilon arbitrarily small, we get an interval whose length is (arbitrarily close to) 1.0.
4)
    
3
{1,4.3,7.2,95.4,534.0}
{72, 83, 19, 25.3, 624.0} 
Returns: 1.4500000000000002

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3565

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6554&pm=3565

Writer:

dgoodman

Testers:

PabloGilberto , lbackstrom , vorthys

Problem categories:

Advanced Math, Search