Connection Status:
Competition Arena > LocalMax

LocalMax

TCCC05 Finals · 2005-01-10 · by dgoodman

TCCC05 Finals · 2005-01-10 · by dgoodman · Advanced Math, Search
Class Name: LocalMax
Return Type: double
Method Name: length
Arg Types: (int, vector<double>, vector<double>)
Problem Statement

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.

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

Submissions are judged against all 61 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class LocalMax with a public method double length(int N, vector<double> xData, vector<double> yData) · 61 test cases · 2 s / 256 MB per case

Submitting as anonymous