Statistics

Problem Statement for "Stamp"

Problem Statement

Little Fox Jiro has a rectangular board. On the board there is a row of N unit cells. The cells are numbered 0 through N-1 from the left to the right. Initially, the cells are not colored. Jiro must color each of the cells red, green, or blue.

You are given a String desiredColor with N characters. For each i, character i of desiredColor represents the color Jiro must use for cell i. If a character is one of 'R' (as red), 'G' (as green), and 'B' (as blue), it means that Jiro must use that particular color. If a character is '*', Jiro may use any of the three colors for the particular cell.

You are also given the ints stampCost and pushCost that describe the cost of the coloring process. The coloring process consists of two phases. In the first phase, Jiro must pick a single stamp he will then use to color all the cells. The length L of the stamp can be any integer between 1 and N, inclusive. A stamp of length L costs L*stampCost.

In the second phase, Jiro must repeatedly use the stamp to color the cells. Each use of the stamp works as follows:

  1. Jiro picks one of the three colors and pushes the stamp into ink of the chosen color C.
  2. Jiro picks a segment of L contiguous cells such that each of them is either uncolored or already has the color C. The segment must be completely inside the board. That is, the leftmost cell of the segment must be one of the cells 0 through N-L.
  3. Jiro pushes the stamp onto the chosen segment of cells. All the cells now have color C.
Each use of the stamp costs pushCost.

Return the smallest possible total cost of coloring all the cells using the above process.

Definition

Class:
Stamp
Method:
getMinimumCost
Parameters:
String, int, int
Returns:
int
Method signature:
int getMinimumCost(String desiredColor, int stampCost, int pushCost)
(be sure your method is public)

Constraints

  • desiredColor will contain between 1 and 50 characters, inclusive.
  • Each character of desiredColor will be either 'R' or 'G' or 'B' or '*'.
  • stampCost will be between 1 and 100,000, inclusive.
  • pushCost will be between 1 and 100,000, inclusive.

Examples

  1. "RRGGBB"

    1

    1

    Returns: 5

    The optimal solution is to choose L=2 and then stamp three times: using red color for cells [0,1], green for [2,3], and blue for [4,5]. The stamp costs 2*1 = 2, each of the three uses costs 1, so the total costs is 2*1 + 3*1 = 5.

  2. "R**GB*"

    1

    1

    Returns: 5

    The optimal solution is the same as in the previous example. Note that you must color all the cells, so choosing L=1 and then using the stamp three times is not a valid solution.

  3. "BRRB"

    2

    7

    Returns: 30

    Also, note that once a cell is colored, you are not allowed to stamp over it using a different color. Therefore, you can only choose L=1 in this case.

  4. "R*RR*GG"

    10

    58

    Returns: 204

    It is allowed to stamp the same cell multiple times if all of those stamps use the same color.

  5. "*B**B**B*BB*G*BBB**B**B*"

    5

    2

    Returns: 33

  6. "*R*RG*G*GR*RGG*G*GGR***RR*GG"

    7

    1

    Returns: 30

  7. "R"

    123

    234

    Returns: 357

  8. "*"

    987

    876

    Returns: 1863

  9. "RR*GG"

    1

    100000

    Returns: 300002

  10. "RR*GG*BB*RR*GG*BB*RR*GG*BB*RR*GG*BB*RR*GG*BB*RR*GG"

    1

    100000

    Returns: 2500002

  11. "RR*GG*BB*RR*GG*BB*RR*GG*BB*RR*GG*BB*RR*GG*BB*RR*"

    1

    100000

    Returns: 1600003

  12. "R**G**B**R**G**B**R**G**B**R**G**B**R**G**B**R*"

    1

    100000

    Returns: 2400002

  13. "*R**G**B**R**G**B**R**G**B**R**G**B**R**G**B**R"

    1

    100000

    Returns: 2400002

  14. "*********R*********G*********R*********B*********"

    1

    100000

    Returns: 500010

  15. "************************B************************"

    1

    100000

    Returns: 100049

  16. "RGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRG"

    100000

    100000

    Returns: 5100000

  17. "**************************************************"

    100000

    100000

    Returns: 1500000

  18. "**************************************************"

    10000

    40000

    Returns: 290000

  19. "**************************************************"

    10000

    70000

    Returns: 380000

  20. "*************************************************"

    100

    151

    Returns: 1755

  21. "*************************************************"

    100

    150

    Returns: 1750

  22. "R************************************************G"

    100000

    100000

    Returns: 1500000

  23. "*****R**********G**********B*****R***************G"

    10000

    100000

    Returns: 600000

  24. "*****R**********G**********B*****R***************G"

    100000

    100000

    Returns: 1500000

  25. "RRRRRRRRRRRRRRRRRRRRRRRRGGGGGGGGGGGGGGGGGGGGGGGGG"

    1

    100000

    Returns: 300024

  26. "G"

    89113

    79630

    Returns: 168743

  27. "RB"

    47185

    16261

    Returns: 79707

  28. "GGBBRR"

    75529

    91787

    Returns: 426419

  29. "BBRRGGBB"

    47574

    53214

    Returns: 308004

  30. "RRRBBBGGGRRRBBB"

    24969

    20906

    Returns: 179437

  31. "*****"

    85934

    3191

    Returns: 101889

  32. "**B***"

    52636

    27801

    Returns: 188675

  33. "B*****R"

    33491

    48378

    Returns: 245607

  34. "RRRGGBBBB"

    2431

    608

    Returns: 7902

  35. "RRRGGBBBB"

    2431

    607

    Returns: 7894

  36. "RRR*RR*RRRRRR*RRBBBBBB*B*BBBBBB*G*GG*GG*GG*GGGGG"

    89322

    89202

    Returns: 1249788

  37. "GG****G*****G*G*BBBB*B****BBBBB**RRR*R***R*R**RR"

    91259

    77666

    Returns: 1196068

  38. "**R****RR*R*RR***B*B******B*B*BB***GGGGGGG****GG"

    67617

    63581

    Returns: 918386

  39. "**GG*GG*GGGGGGGG*GGGGGG*GGGGGGGGGGG**G*G*GGGGGG"

    18541

    45191

    Returns: 403256

  40. "RRRRR**R*RRRRR**RR***RRR*RRR****RR*RRR*R*RR*RRR"

    76962

    93536

    Returns: 1176912

  41. "R*RR*RR**R****R*RR*R**R**R*R*R**RRR*R***R**R*RR"

    76733

    19856

    Returns: 545204

  42. "R*RR*RRB*BBB*BGGG*G***RR*R*RBB*BB**GGGGGGGRRRRRRR"

    20379

    21843

    Returns: 295554

  43. "R**R**RB*BBBBB*GGGG*GRR**RR*B*BBBBBGG*GGGG**RRR*R"

    99687

    97099

    Returns: 1377502

  44. "***G*GG*BBB*BBR*R***R******G**B******R***R*G*GGG*"

    56435

    49338

    Returns: 740411

  45. "*RR*R*RR*RRRRR**RRRR*RR*GGGGG*GGGGG*G**GGG*GG*"

    52922

    60897

    Returns: 788758

  46. "G*G**GGG*GG*GG***GGG**GR*RRR*RRRR*R***R*RRRR**"

    35667

    36890

    Returns: 506676

  47. "*G*G***********G*GGG***RR*RRR**RRRR**RRRR*R*R*"

    18414

    29955

    Returns: 327042

  48. "B*RRGGB**RGG*BRRGGBBRRGGB**RG*BB**GGBB*RG*BBRRGG"

    12524

    48143

    Returns: 1180480

  49. "*B*R***BR*GGB*R*G***R*GG**R*G**B*R*GB**R*GBB****"

    16490

    12745

    Returns: 338860

  50. "**GGBB*R*******G****G*BB*R***BR****B*R**B**R**B*"

    62615

    99861

    Returns: 1885482

  51. "*********B**R***************************G*********"

    57169

    20171

    Returns: 487555

  52. "*B***********************G**RB******************R"

    26694

    94313

    Returns: 1683403

  53. "****R********GB*************G**R*R*B************"

    7245

    51166

    Returns: 547885

  54. "*********B**G**R*******G********R****B*********"

    42925

    5343

    Returns: 214082

  55. "*******G*B******R****G*RB***R***G*G*R******B**B"

    95614

    32088

    Returns: 961340

  56. "BR*R*R**B***R***BRG***G*BB*G***G****G*R***GB***"

    13610

    7350

    Returns: 359060

  57. "RR****BBBB****R***R*R*G**GR**BGG**B*GB*GRRBG**G"

    76223

    87458

    Returns: 4186749

  58. "RRRRRRRRRRRRRGGGGGGGGGGGGGGGGGBBBBBBBBBBBBBBBBBBB"

    138

    7

    Returns: 458

  59. "RRRRRRRRRRRRRGGGGGGGGGGGGGGGGGBBBBBBBBBBBBBBBBBBB"

    138

    6

    Returns: 432

  60. "RRRRRRRRRRRRRGGGGGGGGGGGGGGGGGBBBBBBBBBBBBBBBBBBB"

    1115

    49

    Returns: 3504

  61. "RRRRRRRRRRRRRGGGGGGGGGGGGGGGGGBBBBBBBBBBBBBBBBBBB"

    1115

    48

    Returns: 3467

  62. "RRRRRRRRRRRRRGGGGGGGGGGGGGGGGGBBBBBBBBBBBBBBBBBBB"

    5

    4

    Returns: 67

  63. "RRRRRRRRRRRRRGGGGGGGGGGGGGGGGGBBBBBBBBBBBBBBBBBBB"

    5

    3

    Returns: 58

  64. "RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRGGGGGGGGGGG"

    1385

    58

    Returns: 4278

  65. "RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRGGGGGGGGGGG"

    1385

    57

    Returns: 4235

  66. "RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRGGGGGGGGGGG"

    1351

    2027

    Returns: 24996

  67. "RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRGGGGGGGGGGG"

    1351

    2026

    Returns: 24990

  68. "RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRGGGGGGGGGGG"

    2887

    722

    Returns: 20934

  69. "RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRGGGGGGGGGGG"

    2887

    721

    Returns: 20918

  70. "RRRRRRRRRRRRRRRRRRRRRRRGGGGGGGGGGGGGGGGGGGGGGGBBBB"

    919

    184

    Returns: 6068

  71. "RRRRRRRRRRRRRRRRRRRRRRRGGGGGGGGGGGGGGGGGGGGGGGBBBB"

    919

    183

    Returns: 6051

  72. "RRRRRRRRRRRRRRRRRRRRRRRGGGGGGGGGGGGGGGGGGGGGGGBBBB"

    1481

    186

    Returns: 7791

  73. "RRRRRRRRRRRRRRRRRRRRRRRGGGGGGGGGGGGGGGGGGGGGGGBBBB"

    1481

    185

    Returns: 7772

  74. "****RRRRR***B*BBB***GGGG*GGGBBB**BBGGGG***RR*RR*RR"

    48

    52

    Returns: 804

  75. "R*****"

    1

    100000

    Returns: 100006

  76. "R**GGBBB"

    5

    10

    Returns: 60

  77. "*R*G*B*"

    11

    100

    Returns: 422

  78. "R*G*B*R*G*B*R*G*B*R*G*B*R*G*B*R*G*B*R*G*B*R*G*B*RB"

    13

    3

    Returns: 163

  79. "RRR***G"

    5

    10

    Returns: 45

  80. "*R*RG*G*GR*RGG*G*GG****R***RRGGGRRRR*G**G"

    35

    142

    Returns: 2377

  81. "RBGRBGRBGRBGRBGRBGRBGRBGRBGRBGRBGRBGRBGRBGRBGRGBRG"

    100000

    100000

    Returns: 5100000

  82. "****B*GB****R"

    10000

    1

    Returns: 10013

  83. "*********R**********B*********G***********R*******"

    3

    5

    Returns: 55

  84. "RR*BB"

    100

    10000

    Returns: 30200

  85. "***"

    10000

    1

    Returns: 10003

  86. "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"

    1

    100000

    Returns: 100050

  87. "**************************************"

    12

    6

    Returns: 108

  88. "**R***BG**G*R**B*G*G***RB**G****"

    1

    20

    Returns: 263

  89. "RR*B"

    1

    5

    Returns: 12

  90. "R***G"

    1

    100

    Returns: 302

  91. "*R*RG*G*GR*RGG*G*GGR***RR*GG*R*RG****GR***RR*GG"

    43

    54

    Returns: 1101

  92. "R************************GB***********************"

    1

    20

    Returns: 93

  93. "******B***R***R*B**"

    2

    7

    Returns: 43

  94. "GG*RR"

    1

    1000

    Returns: 3002

  95. "G****BR**B"

    25142

    76188

    Returns: 431224

  96. "RR*GGBBB"

    1

    10

    Returns: 52

  97. "G**RB*R*B*BG*B*B*B******R*R*****BG**"

    14

    1

    Returns: 47

  98. "**RR*GGGRRR***********BB***R"

    66576

    2671

    Returns: 141364

  99. "R*G"

    1

    100000

    Returns: 300001

  100. "RRRRRR"

    1

    1000

    Returns: 1006

  101. "**************************************************"

    986

    34123

    Returns: 83423

  102. "RRRRRR"

    1

    100000

    Returns: 100006

  103. "**RR*R**R*G****RRBB****BB****R*G*G*GG****BBBBB***"

    20

    30

    Returns: 500

  104. "R*BGGRRBB"

    1

    100000

    Returns: 900001

  105. "RG"

    100000

    100000

    Returns: 300000

  106. "R*B"

    1

    100

    Returns: 301

  107. "RR**R**BB"

    1

    1000

    Returns: 3003

  108. "R*****G"

    1

    100000

    Returns: 300003

  109. "**************************************************"

    1

    1

    Returns: 15

  110. "******"

    1

    100

    Returns: 106

  111. "R"

    1

    2

    Returns: 3

  112. "***********************************************RGR"

    10000

    1

    Returns: 10050

  113. "*************B*********G************GG"

    4

    10

    Returns: 80

  114. "R****BGGGG"

    1

    999

    Returns: 3999

  115. "G*GR**B*BRBG*RRBG*RGGR**"

    79052

    13175

    Returns: 395252

  116. "BR*B*"

    98

    513

    Returns: 2663

  117. "R*G"

    1

    100

    Returns: 301

  118. "****************G*********************************"

    1000

    1000

    Returns: 15000

  119. "RRRRRRRRRRRRRRRRRRRRRRRGRRRRRRRRRRRRRRRRRRRRRRRRRR"

    10000

    10000

    Returns: 510000

  120. "RGBRGBRGB"

    65536

    65536

    Returns: 655360

  121. "RRRRRRRRRRBRRRRRRRRRR"

    7

    98744

    Returns: 2073631

  122. "*"

    1

    1

    Returns: 2

  123. "RR*R*B***"

    12190

    25377

    Returns: 124891

  124. "************************************R*************"

    11

    12

    Returns: 170

  125. "B*G"

    1

    10000

    Returns: 30001

  126. "RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR"

    1

    50000

    Returns: 50050

  127. "R*G"

    1

    10000

    Returns: 30001

  128. "RRR*GGG"

    1

    100000

    Returns: 300003

  129. "R**RRRR***GGGGG"

    13

    19

    Returns: 122

  130. "*****************************************RR**GR*G*"

    100000

    100000

    Returns: 2700000

  131. "**"

    1

    100

    Returns: 102

  132. "*RGB*"

    4

    4

    Returns: 24

  133. "RRRBBBBGGGGRRRRBBBB"

    1

    10000

    Returns: 90003

  134. "*GG*B**B**B*BB*G*BBB**B**B**B**B**B*BB*G*BBB**B**B"

    7

    1

    Returns: 38

  135. "RRRR"

    2

    1000

    Returns: 1008

  136. "RRBRR"

    1

    100

    Returns: 501

  137. "R*B"

    3

    100

    Returns: 303

  138. "*R*G*RGG*RRB*B***B**R**G**R**R**R**RGGG*R*G*BG*GR*"

    100000

    100000

    Returns: 2900000

  139. "BB*R*G*BBR*GRR*"

    39197

    70687

    Returns: 1099502

  140. "**************************************************"

    1

    100000

    Returns: 100050

  141. "RR**GRRRR*"

    1

    1

    Returns: 8

  142. "R***B"

    1

    1000

    Returns: 3002

  143. "*************"

    1

    1

    Returns: 8

  144. "BRR***BBRR***GGG**RR**BBB****RRR"

    1

    1

    Returns: 33

  145. "**************************************************"

    4

    7

    Returns: 75

  146. "*R*G*B*GR*B*RG*B"

    1

    1867

    Returns: 29873

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: