Algorithm

 Problem Statement for Stamp

Problem link- https://community.topcoder.com/stat?c=problem_statement&pm=11835&rd=15180

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
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
 
5)  
     
"*R*RG*G*GR*RGG*G*GGR***RR*GG"
 
7
 
1
 
Returns: 30

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <string>

using namespace std;

class Stamp {
public:
  int getMinimumCost(string desiredColor, int stampCost, int pushCost) {
    long long ret = 2e18;
    for(int L = 1; L <= desiredColor.length(); ++L)
      ret = min(ret, 1ll * pushCost * check(L, desiredColor) + 1ll * stampCost * L);
    return ret;
  }

  int check(int L, string desiredColor) {
    char all[desiredColor.length()];
    for(int i = 0; i < desiredColor.length(); ++i)
      all[i] = ' ';

    int cnt = 0;
    for(int i = 0; i < desiredColor.length();) {
      char ch = ' ';
      int j;

      for(j = i; j < i + L; ++j) {
        if(ch != ' ' && desiredColor[j] != ch && desiredColor[j] != '*')
          break;

        if(ch == ' ' && desiredColor[j] != '*')
          ch = desiredColor[j];

        if(ch != ' ')
          all[j] = ch;
      }

      if(j == i + L) {
        i += L, ++cnt;
        continue;
      }

      int tmp = j;

      int need = (i + L) - j, s = i - need;
      if(s < 0)
        return 1e9;

      for(j = i - 1; j >= s; --j) {
        if(ch != ' ' && all[j] != ' ' && all[j] != ch)
          if(!solve(L, desiredColor, j, all))
            return 1e9;

        if(ch != ' ' && desiredColor[j] != ch && desiredColor[j] != '*')
          return 1e9;

        if(ch == ' ' && desiredColor[j] != '*')
          ch = desiredColor[j];

        if(ch != ' ')
          all[j] = ch;
      }
      
      i = tmp, ++cnt;
    }
    
    return cnt;
  }

  bool solve(int L, string desiredColor, int j, char all[]) {
    if(j - L < 0)
      return false;

    char ch = ' ';
    if(desiredColor[j] != '*')
      ch = desiredColor[j];

    for(int k = j - 1; k >= j - L; --k) {
      if(all[k] != ' ' && ch != ' ' && all[k] != ch)
        if(!solve(L, desiredColor, k, all))
          return false;

      if(ch != ' ' && desiredColor[k] != ch && desiredColor[k] != '*')
        return false;

      if(ch == ' ' && desiredColor[k] != '*')
        ch = desiredColor[k];

      if(ch != ' ')
        all[k] = ch;
    }

    return true;
  }
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
"RRGGBB"
1
1

Output

x
–
+
cmd
5
Advertisements

Demonstration

TopCoder Solution SRM558-D1-250 Statement for Stamp C,C++, Java, Js and Python ,SRM558-D1-250,TopCoder Solution