TopCoder problem "CountingCrowds" used in TCHS07 Beta 1 (Division I Level Two)



Problem Statement

    

Old Mr. Simpson is a well known teacher at your high school. During classes, he only stares at the blackboard, so a lot of students sneak out of class through the door. In order to count the number of people sneaking out, he has installed a sensor above the door. Once every second, the sensor records the height of the person underneath it. If there are multiple people underneath the sensor at the same time, it will record only the height of the tallest one. Mr. Simpson has asked you to write a program to interpret the data recorded by the sensor. He wants to know how many people are leaving through the door. You will try to minimize your answer without lying to your teacher.

You will be given a String[] sensorData. Concatenate all the elements of sensorData to produce one long string. The ith character of this string is the height measured by the sensor at the ith second. '.' means there was nobody underneath the sensor. 'A'-'Z' represent different heights. Lower letters represent taller heights, so 'A' is the tallest height and 'Z' is the shortest height. Assume that everybody who goes through the door is leaving. Also, note that people may pass through the door at different speeds. For example, if the sensor data reads "..BBAABB..", it could mean that a person of height B took six seconds to go through the door, and during that same time, a taller person of height A went through the door in just two seconds. Return the minimum possible number of people who could have left through the door.

 

Definition

    
Class:CountingCrowds
Method:minimalInterpretation
Parameters:String[]
Returns:int
Method signature:int minimalInterpretation(String[] sensorData)
(be sure your method is public)
    
 

Constraints

-sensorData will contain between 1 and 50 elements, inclusive.
-Each element of sensorData will contain between 1 and 50 characters, inclusive.
-Each character in sensorData will be either '.' (dot) or an uppercase letter ('A'-'Z').
 

Examples

0)
    
{"..BBAABB.."}
Returns: 2
The example explained in the statement.
1)
    
{"..AAA","AA.."}
Returns: 1
The data may be split in different strings.
2)
    
{"CCB..ABC.ACDACD.."}
Returns: 10
3)
    
{"KHTXRJNHKPHNDWEGOQKGFSQWWFSBNZSHJJHTOZK","RRPPPEBOPFZXVMLHYDNIEIZNQWYAUYB"}
Returns: 58

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10705&pm=7515

Writer:

tywok

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Simple Search, Iteration, Simulation