TopCoder problem "Measures" used in SRM 284 (Division II Level Two)



Problem Statement

    We are producing music analysis software. We have already broken the sensor data into a sequence of beats, with the loudness of each beat known.Your project is to divide the beats into measures. Each measure consists of adjacent beats, and each beat must be in exactly one measure. The number of beats per measure must be between 2 and 10, inclusive, and be the same for all measures.

The heuristic that has been chosen is to divide the beats into measures based upon the idea that the first beat in each measure tends to be stressed. The data does not necessarily begin or end with a full measure, so if you decide on k beats per measure then the first full measure may begin at any of the first k beats in the loudness data. The primary requirement is that at least 80% of the full measures must have the loudness of their first beat at least as big as the loudness of each of the other beats in that measure. It is also required that there must be at least one full measure.

Create a class Measures that contains a method beatsPerM that is given a int[] loudness giving the loudness of each beat. It returns the smallest acceptable number of beats per measure. Return -1 if no value between 2 and 10 inclusive satisfies the requirements.

 

Definition

    
Class:Measures
Method:beatsPerM
Parameters:int[]
Returns:int
Method signature:int beatsPerM(int[] loudness)
(be sure your method is public)
    
 

Constraints

-loudness will contain between 2 and 50 elements, inclusive.
-Each element of loudness will be between 0 and 100, inclusive.
 

Examples

0)
    
{3,9,3,0,9,3,1,9,11}
Returns: 3
[partial-measure, 9/3/0, 9/3/1, partial-measure] satisfies the requirements since each of the 2 full measures has its stress on the first beat.
1)
    
{3,9,3,0,9,3,1,9,11,1}
Returns: 5
[partial-measure, 9/3/0/9/3, partial-measure] satisfies the requirements. The best attempt at forming measures with fewer than 5 beats per measure would be 3 beats per measure starting at the 2nd beat, but this would result in 3 full measures, 1 of which would not have its first beat stressed; this would violate the 80% requirement.
2)
    
{5,2,5,2,8,6,3,5,5,1,9,0,2}
Returns: 2
[5/2, 5/2, 8/6, 3/5, 5/1, 9/0, partial-measure] has 5/6 of its measures having their first beat stressed, so it satisfies the "at least 80%" rule.
3)
    
{3,9,65,2,8,7,66,22,11,43,26,77,78,79,80,81,82,83,3,5,8,9,4,20,21,22,23}
Returns: -1
4)
    
{1,6,9}
Returns: -1
Using 3 beats per measure we could break this into [partial measure, partial measure] but we are required to have at least 1 full measure.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8081&pm=2267

Writer:

dgoodman

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Brute Force