Statistics

Problem Statement for "ColorTheCells"

Problem Statement

There are N cells in a row. The cells are numbered 0 through N-1 from left to right. Magical Girl Riena wants to give magical powers to all the cells by painting all of them using magic colors. Riena starts at time 0 in cell 0. She can do three types of actions:
  • She can wait in her current cell for as long as she wants.
  • She may move to an adjacent cell. The move takes 1 unit of time.
  • She may paint an adjacent cell. Painting the cell takes 1 unit of time. (Note that she cannot paint the cell she currently stands in, only the adjacent ones.)
There is one additional restriction: Riena cannot enter a freshly painted cell until the paint dries. You are given a int[] dryingTime with N elements. For each i, dryingTime[i] is the time needed for the paint in the cell i to dry after Riena finished painting the cell. Once cell i has already been painted, Riena is not allowed to start moving to cell i before the paint in cell i gets dry.
For example, suppose that Riena is currently in cell 3 and we have dryingTime[2]=7. At time 12 Riena starts painting the adjacent cell 2. She will finish painting the cell at time 12+1 = 13. The paint in the cell will be dry at time 13+7 = 20. Therefore, the earliest time Riena can be in cell 2 again is 21. (At time 20 she can start moving from cell 3 to cell 2, and the move takes 1 unit of time.)
Riena wants to paint all N cells, and she wants to finish painting as quickly as possible. She may paint the cells in any order she likes. Compute and return the earliest possible time when Riena can finish painting the last cell. (Note that the return value you are trying to minimize is the moment when Riena finishes painting, not the moment when the paint dries.)

Definition

Class:
ColorTheCells
Method:
minimalTime
Parameters:
int[]
Returns:
int
Method signature:
int minimalTime(int[] dryingTime)
(be sure your method is public)

Constraints

  • dryingTime will contain between 2 and 7 elements, inclusive.
  • Each element of dryingTime will be between 1 and 100,000, inclusive.

Examples

  1. {2, 2, 3}

    Returns: 6

    One of the optimal solutions: At time 0, Riena starts moving from cell 0 to cell 1. At time 1, she reaches cell 1 and starts painting cell 0. At time 2, she finishes painting cell 0 and starts painting cell 2. The paint in cell 0 starts drying. At time 3, Riena finishes painting cell 2. The paint in cell 2 starts drying. Riena now has to wait because she already painted both adjacent cells and she cannot move to either of them yet. At time 4, cell 0 becomes dry and Riena starts moving from cell 1 to cell 0. At time 5, Riena reaches cell 0 and starts painting cell 1. At time 6, Riena finishes painting cell 1 and she is done. (Also, cell 2 is now dry and cell 1 will be dry at time 8, but we don't care about them any more.)

  2. {1, 2, 100, 1}

    Returns: 7

  3. {33, 58, 21, 44}

    Returns: 26

  4. {35198, 26281, 72533, 91031, 44326, 43178, 85530}

    Returns: 26287

  5. {4, 3}

    Returns: 6

  6. {5, 5}

    Returns: 8

  7. {5, 6}

    Returns: 9

  8. {5, 7}

    Returns: 9

  9. {5, 8}

    Returns: 9

  10. {5, 9}

    Returns: 9

  11. {6, 5}

    Returns: 8

  12. {6, 6}

    Returns: 9

  13. {6, 7}

    Returns: 10

  14. {6, 8}

    Returns: 10

  15. {6, 9}

    Returns: 10

  16. {7, 5}

    Returns: 8

  17. {7, 6}

    Returns: 9

  18. {7, 7}

    Returns: 10

  19. {7, 8}

    Returns: 11

  20. {7, 9}

    Returns: 11

  21. {8, 5}

    Returns: 8

  22. {8, 6}

    Returns: 9

  23. {8, 7}

    Returns: 10

  24. {8, 8}

    Returns: 11

  25. {8, 9}

    Returns: 12

  26. {9, 5}

    Returns: 8

  27. {9, 6}

    Returns: 9

  28. {9, 7}

    Returns: 10

  29. {9, 8}

    Returns: 11

  30. {9, 9}

    Returns: 12

  31. {10, 7, 4}

    Returns: 8

  32. {7, 5, 8}

    Returns: 9

  33. {7, 10, 7}

    Returns: 11

  34. {9, 4, 5}

    Returns: 8

  35. {4, 7, 10, 8}

    Returns: 8

  36. {8, 10, 8, 7}

    Returns: 12

  37. {4, 4, 6, 8}

    Returns: 8

  38. {7, 9, 4, 5}

    Returns: 9

  39. {5, 7, 5, 7, 6}

    Returns: 11

  40. {8, 4, 7, 10, 9}

    Returns: 10

  41. {4, 4, 5, 10, 4}

    Returns: 10

  42. {10, 8, 5, 6, 6}

    Returns: 12

  43. {10, 9, 7, 5, 5, 10}

    Returns: 13

  44. {4, 9, 8, 8, 4, 7}

    Returns: 12

  45. {5, 6, 6, 7, 7, 8}

    Returns: 13

  46. {10, 8, 5, 5, 6, 9}

    Returns: 13

  47. {9, 4, 8, 7, 5, 7, 5}

    Returns: 16

  48. {8, 9, 6, 10, 6, 9, 5}

    Returns: 15

  49. {8, 9, 5, 7, 4, 6, 4}

    Returns: 15

  50. {10, 4, 5, 4, 8, 7, 7}

    Returns: 14

  51. {48465, 33816, 35469, 39940, 25809, 98600, 75035}

    Returns: 25819

  52. {11081, 62918, 86539, 5338, 19997, 3473, 3177}

    Returns: 3185

  53. {96353, 23736, 13308, 92210, 15990, 27781, 36073}

    Returns: 13316

  54. {34527, 15439, 14021, 15858, 66113, 43959, 68727}

    Returns: 14029

  55. {47505, 66210, 44519, 82569, 47908, 92235, 90233}

    Returns: 44527

  56. {98999, 4191, 10501, 7485, 96772, 8659, 61558}

    Returns: 4197

  57. {75855, 34569, 61057, 97916, 26057, 83188, 77847}

    Returns: 26067

  58. {2056, 81673, 93540, 53008, 7253, 6426, 84186}

    Returns: 2060

  59. {52915, 75838, 4095, 27212, 22309, 72134, 86659}

    Returns: 4103

  60. {36044, 7979, 3543, 61328, 53591, 65769, 66468}

    Returns: 3551

  61. {79848, 34700, 68268, 14435, 4421, 32812, 88191}

    Returns: 4431

  62. {32667, 3039, 45934, 79407, 63102, 47154, 59863}

    Returns: 3045

  63. {1800, 30041, 95391, 38335, 96059, 4768, 40581}

    Returns: 1804

  64. {76361, 33954, 47506, 99134, 76312, 96553, 41557}

    Returns: 33960

  65. {34765, 15657, 38173, 53993, 10570, 57049, 23896}

    Returns: 10580

  66. {73302, 73302, 73304}

    Returns: 73306

  67. {90634, 90636, 90635}

    Returns: 90638

  68. {50467, 50473, 50467}

    Returns: 50471

  69. {69686, 69683, 69685}

    Returns: 69687

  70. {15193, 15194, 15196, 15198}

    Returns: 15197

  71. {44460, 44453, 44454, 44453}

    Returns: 44458

  72. {68324, 68317, 68316, 68316}

    Returns: 68321

  73. {26992, 26990, 26990, 26994}

    Returns: 26995

  74. {76938, 76943, 76945, 76939, 76936}

    Returns: 76942

  75. {54062, 54061, 54059, 54058, 54061}

    Returns: 54064

  76. {82783, 82790, 82786, 82790, 82788}

    Returns: 82787

  77. {66514, 66515, 66517, 66521, 66519}

    Returns: 66518

  78. {50756, 50751, 50753, 50754, 50751, 50756}

    Returns: 50757

  79. {60230, 60224, 60230, 60227, 60232, 60225}

    Returns: 60230

  80. {90220, 90214, 90222, 90216, 90218, 90214}

    Returns: 90220

  81. {92298, 92291, 92292, 92290, 92297, 92292}

    Returns: 92297

  82. {74572, 74568, 74573, 74568, 74574, 74570, 74570}

    Returns: 74574

  83. {13773, 13773, 13773, 13773, 13780, 13773, 13772}

    Returns: 13777

  84. {7136, 7142, 7135, 7141, 7139, 7141, 7136}

    Returns: 7140

  85. {90118, 90126, 90120, 90118, 90120, 90117, 90117}

    Returns: 90122

  86. {59938, 59938, 59950, 59943, 59949, 59937, 59936}

    Returns: 59942

  87. {13869, 13858, 13857, 13857, 13869, 13857, 13862}

    Returns: 13864

  88. {45123, 45118, 45122, 45128, 45119, 45129, 45129}

    Returns: 45124

  89. {96358, 96351, 96353, 96359, 96353, 96358, 96349}

    Returns: 96357

  90. {27258, 27253, 27264, 27261, 27268, 27258, 27257}

    Returns: 27259

  91. {25293, 25299, 25308, 25306, 25301, 25291, 25303}

    Returns: 25297

  92. {69437, 69441, 69439, 69447, 69436, 69442, 69445}

    Returns: 69441

  93. {30548, 30547, 30558, 30554, 30560, 30551, 30558}

    Returns: 30552

  94. {66311, 66308, 66314, 66315, 66313, 66304, 66308}

    Returns: 66312

  95. {28337, 28341, 28328, 28334, 28330, 28328, 28330}

    Returns: 28336

  96. {83903, 83892, 83899, 83896, 83904, 83903, 83891}

    Returns: 83898

  97. {11732, 11738, 11746, 11734, 11741, 11734, 11740}

    Returns: 11736

  98. {41914, 41905, 41906, 41905, 41905, 41913, 41905}

    Returns: 41911

  99. {53504, 53497, 53498, 53495, 53499, 53502, 53496}

    Returns: 53503

  100. {6063, 6057, 6061, 6058, 6056, 6068, 6063}

    Returns: 6063

  101. {74904, 74909, 74919, 74916, 74921, 74906, 74909}

    Returns: 74908

  102. {89388, 89383, 89387, 89399, 89391, 89395, 89391}

    Returns: 89389

  103. {95560, 95552, 95560, 95546, 95550, 95556, 95549}

    Returns: 95556

  104. {17562, 17557, 17562, 17566, 17563, 17559, 17559}

    Returns: 17563

  105. {38844, 38842, 38836, 38853, 38845, 38852, 38849}

    Returns: 38844

  106. {35198, 26281, 72533, 91031, 44326, 43178, 85530 }

    Returns: 26287

  107. {2, 2, 3 }

    Returns: 6

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: