TopCoder problem "CompositionTimeSignature" used in TCHS SRM 4 (Division I Level Two)



Problem Statement

    

In music, each note has a relative duration. For example, a whole note lasts four times longer than a quarter note. Half notes, eighth notes, and sixteenth notes have one half, one eighth, and one sixteenth the duration of whole notes, respectively.

A musical composition is characterized by its time signature, which defines the number of beats per measure. Time signatures are written as fractions, where the numerator is the number of beats, and the denominator is the type of note represented by each beat. For example, a time signature of 2/4 indicates that each measure contains two beats, each of which are quarter notes. A time signature of 3/8 indicates that each measure contains three beats, each of which are eighth notes. For the purposes of this problem, we will only consider the following time signatures: 3/8, 2/4, 3/4 and 4/4.

It is difficult for an untrained musician to determine the time signature of a composition. It is even more difficult for a computer. You will be given a String duration containing the description of a composition. Each character of duration corresponds to a single note in the composition. 'W' denotes a whole note, 'H' a half note, 'Q' a quarter note, 'E' an eighth note, and 'S' a sixteenth note.

Determine the time signature of the composition using the following heuristic algorithm (which is not very good, but quite simple):

  1. Consider all the available time signatures (3/8, 2/4, 3/4 and 4/4). Keep only the time signatures for which the composition would contain an integral number of measures, and discard the rest.
  2. For each of the remaining time signatures, determine the number of notes in the composition that start and end in different measures. Keep only the time signatures for which this number is minimal.
  3. Select the smallest of the remaining time signatures (where 3/8 < 2/4 < 3/4 < 4/4).

Return the time signature as a String ("3/8", "2/4", "3/4", or "4/4"), or return "?/?" (quotes for clarity only) if there are no time signatures left after step 1.

 

Definition

    
Class:CompositionTimeSignature
Method:getTimeSignature
Parameters:String
Returns:String
Method signature:String getTimeSignature(String duration)
(be sure your method is public)
    
 

Constraints

-duration will have between 1 and 50 characters, inclusive.
-Each character in duration will be 'W', 'H', 'Q', 'E' or 'S'.
 

Examples

0)
    
"QQEEQEEEQEQ"
Returns: "4/4"

The total duration of the composition (in whole notes) is:

1/4+1/4+1/8+1/8+1/4+1/8+1/8+1/8+1/4+1/8+1/4 = 2.

The number of measures in the composition for different time signatures is:

  • for time signature 3/8: 2/(3/8) = 5 1/3 measures;
  • for time signature 2/4: 2/(2/4) = 4 measures;
  • for time signature 3/4: 2/(3/4) = 2 2/3 measures;
  • for time signature 4/4: 2/(4/4) = 2 measures.

So only time signatures 2/4 and 4/4 will be left after the first step of the algorithm. For time signature 2/4 the composition looks like this ('|' characters denote measure dividers, and 'Q' and 'E' characters show when each note starts):" 

 Q   Q    E E Q    E E E Q    E Q   
|        |        |        |        |
|        |        |        |        |
|        |        |        |        |

For time signature 4/4 the composition looks like this:

 Q   Q   E E Q    E E E Q   E Q   
|                |                |
|                |                |
|                |                |

So the number of notes that start and end in different measures is 1 for time signature 2/4 and 0 for time signature 4/4. Therefore only time signature 4/4 is left after the second step of the algorithm.

1)
    
"S"
Returns: "?/?"
The composition is very short and will occupy less than one measure for any time signature.
2)
    
"EEEEEEEEEEEEEEEEEEEEEEEE"
Returns: "3/8"
The first two steps of the algorithm will not throw away any time signatures. So the smallest possible time signature 3/8 will be chosen on the third step.
3)
    
"QQQQQQQQQQQQ"
Returns: "2/4"
Here 3/8 and 3/4 will be thrown away after the second step of the algorithm and the smallest time signature among 2/4 and 4/4 will be chosen on the third step.
4)
    
"EQHQQWEEHSEEQWQEHHEEQSQEQHESQSWQESQEWWSSHQWQHQWSQW"
Returns: "3/4"

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10023&pm=6423

Writer:

ivan_metelsky

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Simple Math, Simple Search, Iteration