TopCoder problem "SpeedTyper" used in SRM 290 (Division II Level One)



Problem Statement

    

Johnny wants to become a great programmer, so he practices to improve his programming skills all the time. He thinks he can save a lot of time if he can learn to type faster. It's said that the key to speed typing is keeping the rhythm, which means pressing each key after a constant interval of time. Johnny, like many programmers, loves all kinds of statistics, so he created a program for measuring his typing progress. The program receives a String letters and a int[] times, representing the keys he pressed and the time of each press in milliseconds respectively. The ith element of times is the time at which he typed the ith character in letters. No key is pressed more than once, and all the times are relative to the start of his practice session.

For this problem you may assume that the average time of one key press will be an integer.

Your task is to calculate which letters take Johnny more than average time to type, so he can practice those letters more. Return a String containing all such letters in the order that they occur in the input.

 

Definition

    
Class:SpeedTyper
Method:lettersToPractice
Parameters:String, int[]
Returns:String
Method signature:String lettersToPractice(String letters, int[] times)
(be sure your method is public)
    
 

Notes

-The time needed to press the first key is given by times[0], and the time needed to press the key corresponding to times[i] for all i > 0 is times[i]-times[i-1].
 

Constraints

-letters will contain only lowercase letters ('a'-'z').
-letters will contain between 1 and 26 characters, inclusive.
-times will contain the same number of elements as the number of characters in letters.
-No letter will occur more than once in letters.
-Each element of times will be between 1 and 100000.
-Elements of times will be in strict ascending order.
-The average time of one key press will be an integer.
 

Examples

0)
    
"dcab"
{250, 300, 400, 800}
Returns: "db"
It took Johnny 250 ms to type 'd', 50 ms to type 'c', 100 ms to type 'a' and 400 ms for 'b'. The average time to type a letter is 200 ms so he needs to practice 'd' and 'b' more.
1)
    
"keyboard"
{100,200,300,500,600,800,900,1200}
Returns: "bad"
It took 200 ms each to type 'b', 'a', 300 ms to type 'd', while it only took 100 ms to type each of the other letters. The average time is 150 ms.
2)
    
"rewq"
{500, 1000, 1500, 4000}
Returns: "q"
'q' seems to be a difficult letter to type.
3)
    
"abc"
{2000, 4000, 6000}
Returns: ""
Though the speed is not too impressive, the rhythm is perfect.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9811&pm=5982

Writer:

hauser

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Simple Search, Iteration