TopCoder problem "ClapLight" used in SRM 196 (Division I Level One , Division II Level Two)



Problem Statement

    I have a light that changes from on to off or from off to on when I clap twice. The light's sensor samples the noise level in the room at short intervals and it triggers the light to change whenever it detects a low noise level followed by exactly 2 high noise levels followed by a low noise level.

"High" or "low" is based on a threshold noise level. When the sampled noise level is as high or higher than the threshold level, the noise level is classified as "high"; otherwise it is classified as "low". I have a int[] background that is a typical sequence of sensor readings when normal activity is taking place. I want software that will choose the threshold value so that it has the following properties:

  1. 1) It causes more than 50% of all the values in background to be classified "low".
  2. 2) It is the lowest possible threshold value that satisfies the 50% rule and that does not cause background to trigger the light to change.

Create a class ClapLight that contains a method threshold that is given the int[] background and that returns the desired threshold value.

 

Definition

    
Class:ClapLight
Method:threshold
Parameters:int[]
Returns:int
Method signature:int threshold(int[] background)
(be sure your method is public)
    
 

Constraints

-background will contain between 4 and 50 elements inclusive.
-Each element of background will be between 0 and 1000 inclusive.
 

Examples

0)
    
{6,6,6,6,6}
Returns: 7
The threshold must be at least 7 to exceed more than 50% of the samples, and with the threshold set at 7 every reading will be classified "low" and the light will not be triggered.
1)
    
{ 5,8,7,6,12,8,4,3,2,6 } 
Returns: 9
The threshold must exceed at least 6 of these values to satisfy the 50% rule. So it must be at least 7. But with the threshold set at 7 the sequence 5, 8, 7, 6 would trigger the light. A threshold of 8 will allow the sequence 6,12,8,4 to trigger the light. A threshold of 9 will never cause this sequence to trigger the light.
2)
    
{8,8,8,1,1,1,1,1,1,1,1,1,1,1,2,1}
Returns: 2
Remember that the high noise levels must be both preceded and followed by low noise levels to trigger the light.
3)
    
{921,1,5,900,8,813,3,3,3,3,3,3,3,813,813}
Returns: 4

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5071&pm=2340

Writer:

dgoodman

Testers:

zoidal , lbackstrom , brett1479

Problem categories:

Brute Force