TopCoder problem "Symbolic" used in TCCC05 Semi 1 (Division I Level Two)



Problem Statement

    Let I_Zero denote the real interval from 0 to 1/3, including 0 but not including 1/3. Let I_One denote the real interval from 1/3 to 1 including both endpoints.

We have a dynamic system, in which real values are generated by the following rule: xt+1 = f(xt) where f is the function 

               f(x) =  3x        (for x in I_Zero) 
                      (3-3x)/2   (for x in I_One)
The trajectory of a value c is the sequence of real values that would be generated by the system starting with c. These would be c, f(c), f(f(c)), etc. The "itinerary" of c is defined to be the sequence of 0's and 1's indicating whether the corresponding trajectory values are in I_Zero or I_One.

For example, the trajectory of 1/2 is 1/2,3/4,3/8,15/16,3/32,9/32, ... so its itinerary is 1,1,1,1,0,0,...

Given a value and the itinerary of an unknown value c, we would like to determine whether the given value is less than or greater than c. Since an itinerary is an infinite sequence, we will be given only the first part of an itinerary, so it may be impossible to determine whether the given value is smaller or larger than c.

Create a class Symbolic that contains a method compare that is given value as a decimal String and a int[] itin (the first elements in the itinerary of the unknown c). The method returns -1, 0, or 1 depending on whether value is less than c, indeterminate, or greater than c.

 

Definition

    
Class:Symbolic
Method:compare
Parameters:String, int[]
Returns:int
Method signature:int compare(String value, int[] itin)
(be sure your method is public)
    
 

Constraints

-value will contain between 2 and 20 characters inclusive.
-value will consist of a decimal point followed by digits '0'-'9'.
-itin will contain between 1 and 50 elements inclusive.
-Each element of itin will be 0 or 1.
 

Examples

0)
    
".5"
{1,1,1,1,0}
Returns: 0
The first elements of the itinerary of 0.5 match the values in itin, so we cannot determine whether 0.5 is less than, equal to, or greater than c.
1)
    
".300000"
{1,1,1,1,0}
Returns: -1
0.3 is less than 1/3 so it is in I_Zero. c is between 1/3 and 1.0 since its itinerary starts in I_One. So 0.3 is less than c.
2)
    
".6"
{1,1,0,1,0,0}
Returns: 1
The trajectory of .6 is .6,.6,.6,.6,... If c were greater than or equal to .6, then f(c) would be less than or equal to (3 - 3*.6)/2 = .6 and f( f(c) ) would be greater than or equal to .6 which contradicts the fact that the third element of itin is 0. Therefore, .6 must be greater than c.
3)
    
".00"
{0,0,0,0,0}
Returns: 0
Indeterminate: value may either be less than or equal to c. (It cannot be greater than c since a number less than .0 has no itinerary.)
4)
    
".1111111111111111111"
{0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1}
Returns: 0
Be careful about the precision of your calculations.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6550&pm=3499

Writer:

dgoodman

Testers:

PabloGilberto , lbackstrom , vorthys

Problem categories:

Advanced Math, Simple Search, Iteration