TopCoder problem "ShortTaps" used in TCO05 Finals (Division I Level Three)



Problem Statement

    

You want to send some messages of various lengths (specified in the number of minutes it takes to send them), and don't want more than three of them to be completely intercepted. A message is considered to be intercepted if some malevolent person taps your connection the whole time the message is being sent (a partially tapped message won't do this person any good). Assuming that the connection is being tapped during interceptTime consecutive minutes, what's the shortest time you need to send all the messages so at most three of the messages can be completely intercepted?

Each message is sent in one continuous transmission, though any number of messages can be sent in parallel. You can only start sending a message at the beginning of a minute. The messages can be sent in any order.

Create a class ShortTaps containing the method leastTime which takes an int interceptTime and a int[] messageTimes (containing the time in minutes it takes to send each message, respectively) and returns an int, the minimum time needed to send all the messages so that at most three of them can be intercepted.

 

Definition

    
Class:ShortTaps
Method:leastTime
Parameters:int, int[]
Returns:int
Method signature:int leastTime(int interceptTime, int[] messageTimes)
(be sure your method is public)
    
 

Constraints

-interceptTime will be between 1 and 100, inclusive.
-messageTimes will contain between 1 and 50 elements, inclusive.
-Each element in messageTimes will be between 1 and 100, inclusive.
 

Examples

0)
    
10
{2, 3, 4, 5, 6, 7, 8}
Returns: 14
The optimal solution can be achieved by sending the messages according to this scheme: 
Time   Message length
---------------------
  0     2 min, 3 min, 6 min
  3     8 min
  6     5 min
  7     4 min, 7 min
1)
    
20
{14, 2, 9, 14, 17, 1, 3, 10, 5, 9, 25, 8, 11, 7}
Returns: 43
2)
    
40
{30, 40, 50, 60, 70, 80, 90, 100}
Returns: 100
Only the two shortest messages have any chance of being intercepted, so all eight messages can be sent at time 0.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8096&pm=4804

Writer:

Yarin

Testers:

PabloGilberto , lbackstrom , Olexiy

Problem categories:

Dynamic Programming, Greedy