Friday, August 8, 2014

FixedPointTheorem

Problem:

TopCoder Problem Statement - FixedPointTheorem

Overview:

Determine the high and low values of a function when called thousands of time, where the output of one iteration is the input of the next.

Java Source:
01: /*
02: TopCoder
03: Single Round Match: 152
04: Division: 2
05: Level: 1
06: Points: 250
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1765
08: */
09:
10: public class FixedPointTheorem {
11:
12:     // Number of iterations before we being keeping track of high and low.
13:     private static final int SETTLE_CYCLES = 200_000;
14:
15:     // Number of iterations where we do track high and low.
16:     private static final int RANGE_CYCLES = 1000;
17:
18:     // This is the function that we'll be iterating through
19:     private static double fnct(double R, double X) {
20:
21:         return R * X * (1 - X);
22:     }
23:
24:     public double cycleRange(double R) {
25:
26:         double X = 0.25;
27:
28:         // Run through 200,000 iterations to stabilize the function.
29:         for (int i = 1; i < SETTLE_CYCLES; i++) {
30:             X = fnct(R, X);
31:         }
32:
33:         // Grab the first number and set it to both the high and low.
34:         X = fnct(R, X);
35:
36:         double hi = X;
37:         double lo = X;
38:
39:         // Start at 2 since we already grabbed the first one.
40:         for (int i = 2; i < RANGE_CYCLES; i++) {
41:             X = fnct(R, X);
42:             hi = Math.max(hi, X);
43:             lo = Math.min(lo, X);
44:         }
45:
46:         return (hi - lo);
47:     }
48: }
Notes:

Be careful that you call the function exactly 200,000 times when stabilizing it, and exactly 1,000 times when determining the high and low values. An off-by-one error will affect the results of some tests.

Also, be sure that you set the initial range values correctly. After stabilizing, the first call to the function will give you both the max and min values. Then, continue through the remaining 999 calls updating the max and min as appropriate.

Finally, make sure that your function is correct. It doesn't explicitly state it in the problem statement, but the function you want to use is the one given in the sample: F(X) = R * X * (1 -X)

No comments:

Post a Comment