Statistics

Problem Statement for "ShortTaps"

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

  1. 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

  2. 20

    {14, 2, 9, 14, 17, 1, 3, 10, 5, 9, 25, 8, 11, 7}

    Returns: 43

  3. 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.

  4. 100

    {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    Returns: 1601

  5. 100

    {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    Returns: 1601

  6. 100

    {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    Returns: 1501

  7. 100

    {1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    Returns: 1600

  8. 1

    {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    Returns: 17

  9. 10

    {7}

    Returns: 7

  10. 10

    {7,43}

    Returns: 43

  11. 12

    {7,9}

    Returns: 9

  12. 12

    {7,3,13}

    Returns: 13

  13. 8

    {2,3,1,19}

    Returns: 19

  14. 8

    {2,3,5}

    Returns: 5

  15. 1

    {2,3,4,5,6,7,8,9,10,11,2,3,4,5,6,7,8,9,10,11,2,3,4,5,6,7,8,9,10,11,2,3,4,5,6,7,8,9,10,11,2,3,4,5,6,7,8,9,10,11}

    Returns: 11

  16. 20

    {8,9,10,11}

    Returns: 21

  17. 20

    {8,9,10,99,11}

    Returns: 99

  18. 25

    {8,9,10,11,7}

    Returns: 26

  19. 25

    {8,9,10,28,7,11}

    Returns: 28

  20. 30

    {8,9,10,11,7,30}

    Returns: 31

  21. 30

    {8,9,10,23,7,30,31}

    Returns: 31

  22. 30

    {8,9,10,23,7,30,32}

    Returns: 32

  23. 100

    {100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100}

    Returns: 116

  24. 56

    {28,32,97,89,56,17,7,21,40,89,52,20,71}

    Returns: 97

  25. 80

    {42,21,18,27,56,60,63,67,55,61,79,53,66,14,16,71,31,70,76,74,71}

    Returns: 165

  26. 59

    {9,27,8,22,26,16,16,7,48,34,39,27,34,33,36,22,55,29,12,43,42,18,8,33,43,45,20,50,59,38,49,38,59,7,38,55,39,12,56,23,18}

    Returns: 346

  27. 22

    {15,5,21,21,18,7,17,22,18,22,8,22,5,6,16,18,22,10,19,14,17,8,18,11,22,17,19,10,10,20,7,18,21,5,22,17,8,10,20,5,13,7,20,7,13,11}

    Returns: 120

  28. 69

    {88,39,69,70,51,58,60,50,75,60,37,39,25,20,27,59,56,65,9,11,56,6,21,34,12,25,49,57,64,79,65,38,61,11,67,36,13,15,32,18,63,96,73,24}

    Returns: 337

  29. 44

    {33,12,9,36,39,41,27,32,16,40,27,16,42,31,18}

    Returns: 73

  30. 73

    {71,7,25,73,50,73,73,48,16,26,55}

    Returns: 93

  31. 87

    {43,76,34,83,55,58,35,46,87,12,70,9,82,80,50,38,15,52,66,72,73,71,36,70,12,41,71,67,33,28,19,80,15,19,66,29,77,70,74,32}

    Returns: 431

  32. 80

    {46,12,76,7,84,39,66,68,46,51,41,13}

    Returns: 116

  33. 44

    {9,31,15,17,40,25,24,40,22,32,29,35,37,36,40,30,5,26,25,15,37,17,5,12,7,26,13,20,14,37,28,44,9,2,4,20,33,34,43,8,2,41,35,30,39,31}

    Returns: 279

  34. 34

    {24,10,33,17,34,21,19,9,13,28,17,7,15,21,23,8,7,30,8,31,34,17,6,13}

    Returns: 112

  35. 91

    {13,28,43,63,72,51,32,89,53,61,7,21,22,90}

    Returns: 164

  36. 95

    {43,28,50,65,67,25,85,55,8,74,21,63,87,13,16,67,15,29,17,18,59,21,83,94,55,33,27,45,17,64,20,48,74,40,39,32,71,50,84,66,90}

    Returns: 592

  37. 16

    {13,12,15,10,13,8,9,14,15,12,16,16,15}

    Returns: 22

  38. 56

    {32,24,38,38,26,20,39,46,22,34,56,51,33,51,49,49,35,54,14,19,29,13,16,34,24,41,28,32,32,35,52,49,27,54,22,47,33}

    Returns: 248

  39. 72

    {42,28,58,12,48,62,24,64,55,43,22,12,32,52,41,66,67}

    Returns: 142

  40. 6

    {55,1,1,97,4,1,3,1,51,2,95,4,4,83,6,6,3,2,3,1,5,5,2,3,81}

    Returns: 97

  41. 95

    {87,18,15,49,57,88,8,49,37,11,55,28,33,78,71,47,89,48,75,63,7,75,46,86,19,22,58,71,75,83,90,34,12,20,55,86,29,65,69,75,28,90,72,61,88,63,8,95}

    Returns: 598

  42. 63

    {21,17,63,57,25,20,11,50,32,39,35,14,36,47,35,52,55,27,15,25,22,19,21,49,57,21,27,50}

    Returns: 252

  43. 80

    {77,62,32,75,18,68,20,12,35,17,49,41,17,28,7,78}

    Returns: 170

  44. 97

    {75,39,52,34,71,61,18,26,85,34,96,90,20,69,86,80,55,79,98,51,39,13,86,44,18,56,15,89,9,83,95,53,83,91,54,53,74}

    Returns: 417

  45. 49

    {38,8,23,10,32,41,24,42,30,43,47,45,48,10,30,27,34,39,37,32,12,32,43,14,37,48,17,12,45,39,27}

    Returns: 167

  46. 5

    {5,5,5,3,3,3,4,5,4,5,5,3,4,3,3,5,5,4,4,5,4,4,5,4,3,4}

    Returns: 17

  47. 30

    {15,25,26,14,26,13,23,28,10,8,11,21,29}

    Returns: 44

  48. 99

    {88,73,66,93,60,94,67,64,36,42,48,46,69,21,88,18,11,88,88,13,69,60,64,54}

    Returns: 274

  49. 95

    {10,54,85,54,18,19,61,53,14,73,9,17,62,64,60,83,75,47,10,12,26,41,12,93,52,22,89,42,31,80,95,83,46,59,25,73,80,72,79,91,37,53,46,13,35,22,61,54,90}

    Returns: 667

  50. 61

    {21,53,52,55,48,48,15,7,11,61,50,22,52,26,55,16,41,16,40,38,20,28,53,24,45,52,30}

    Returns: 198

  51. 41

    {37,10,23,22,39,17,12,10,24,25,35,26,13,37,34,33,41,40,19,37,23,18,17,41,41,24,31,5,34,4,15,12,27,36,33,32,7}

    Returns: 181

  52. 89

    {37,75,69,4,86,75,74,84,4,21,15,78,9,9,66,65,52,83,7}

    Returns: 192

  53. 60

    {24,46,3,19,29,21,35,3,4,51,56,36,47,54,8,30,25,30,26,27,3,17,41,27,7,6,31,57,59,59,46,32,31,55,12}

    Returns: 307

  54. 70

    {44,37,56,68,46,62,57,55,53,15,41,8,55,22,56,45,19,56,52}

    Returns: 144

  55. 47

    {16,6,46,18,41,11,32,46,19,26,36,30,43,16,30,5,13,24,15}

    Returns: 121

  56. 81

    {23,69,80,15,82,20,60,52,53,31,98,54,45,74,97,72,69,30,68,50,75,91,66,72,75,23,36,19,79,25,74,62,90,68,37,76,65,58,8,16,74,65,58,29,10,31,76,37,15,40}

    Returns: 431

  57. 52

    {10,29,13,51,29,29,24,15,27,12,23,29,16,20,38,30,37,38,31,10,30,48,10,21,13,41,45,16}

    Returns: 220

  58. 22

    {22,18,8,18,12,17,22,12,4,4,10,12,5,13,21,15,15,5,3,14,3,5,15,16,8,8,15,9,20,16,7,21,10,13,20,19,17,6,5,9,9,21,10}

    Returns: 138

  59. 23

    {12,16,8,20,20,23,17,23,17,11,21,18,13,12,10,20,21,16,20,22,21,19,11,23,16,20,21,9,8,8,17,20,9,19,19}

    Returns: 80

  60. 7

    {7,78,7,7,7,6,77,6,7,6,6,6,84,7,62,98,6,63,62,64,6,58,6,86}

    Returns: 98

  61. 36

    {20,10,27,27,23,33,18,11,27,19,31,30,26,29,17,26,27,15,25,21,17,17,36,13,35,24,16,20,29,14,18,27,35,26,29,11,36,16,30,11,13,25,34,19,36,23,32,26}

    Returns: 202

  62. 19

    {11,7,14,9,18,9,13,14,18,11,11,7,10,7,7,13,7,12,15,18,10,7,15,14,14,9,17}

    Returns: 69

  63. 60

    {13,12,22,40,43,59,39,52,27,31,24,57,8,30,4,34,58,31,29,52,7,11,19,6,37,36,43,58,11,46,54,8,23,37,49,60,54,52}

    Returns: 301

  64. 36

    {27,33,30,35,14,70,9,7,5,9,15,2,91,34,16,2,67,29,16,32,83,9,24,28,50,11,22,4,12,31,21,33,35,57,17,26,21,34,19,12,69,73,18,56,81,19,9,14}

    Returns: 197

  65. 10

    {8,9,10,8,8,10,8,8,8,9,10,10,9,10,10,10,8,10,10,10}

    Returns: 18

  66. 37

    {22,21,28,26,32,21,35,35,12,28,34,29,19,27,19,32,27,30,32,11,29,33,33,12,10,26,37,17,16,28,36}

    Returns: 115

  67. 48

    {28,16,36,37,45,25,30,32,39,32,46,8,28,31,11,47,23,16,14,17,40,34,42,17,36,44,23,27,9,37,46,34,17}

    Returns: 193

  68. 73

    {46,40,35,36,67,73,49,68,51,31,71,67,66,62,33,71,16,10,69,49,66,63,14,71,71,13,46,40,70,17,78,50,12,75,59,24,22,98,56,24,61,45,79,79}

    Returns: 304

  69. 55

    {44,48,46,36,28,30,28,43,19,17,16,53,20,9,9,44,27,35,18,18,45,10,20,53,19,13,19,46,29,32,36,51,12,16,20,51,47,22,13,24,29,9,13,44,14,32,50,32}

    Returns: 398

  70. 93

    {73,49,85,81,58,31,88,41,66,32,8,48,24,52,57,43}

    Returns: 189

  71. 15

    {8,7,2,3,8,4,7,13,4,2,13,7,8,4,9,12,10,11,4,7,7,2,6,3,6,3,6,12,15}

    Returns: 76

  72. 91

    {99,61,98,54,60,97,55,11,17,44,15,78,23,72,62,91,29,41,59,27,51,94,11,74,11,31,41,52,59,81,54,65,78,15,89,77,18,72,88,62,61,66}

    Returns: 449

  73. 25

    {25,13,15,12,21,10,7,16,16,13,10,4,20,24,20}

    Returns: 48

  74. 10

    {23,25,28,30,31}

    Returns: 31

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: