Connection Status:
Competition Arena > Stamp

Stamp

SRM 558 · 2012-06-05 · by ir5

SRM 558 · 2012-06-05 · by ir5 · Dynamic Programming
Class Name: Stamp
Return Type: int
Method Name: getMinimumCost
Arg Types: (string, int, int)
Problem Statement

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.

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
0)
"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.

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

2)
"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.

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

4)
"*B**B**B*BB*G*BBB**B**B*"
5
2
Returns: 33

Submissions are judged against all 146 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Stamp with a public method int getMinimumCost(string desiredColor, int stampCost, int pushCost) · 146 test cases · 2 s / 256 MB per case

Submitting as anonymous