TopCoder problem "MiniPaint" used in SRM 178 (Division I Level Three)



Problem Statement

    You have been given a String[] picture. Each character in picture represents a space in the picture. A 'B' designates a space that needs to be painted black, and a 'W' denotes a space that must be painted white. The painting device you have been given only makes horizontal strokes, of any length, exactly one space high. In addition, it can only use 1 color at a time. Due to the nature of the paint, a space cannot be painted twice. For example, the following picture could be colored in 6 distinct strokes:
picture = {"BBBBBBBBBBBBBBB",
           "WWWWWWWWWWWWWWW",
	   "WWWWWWWWWWWWWWW",
           "WWWWWBBBBBWWWWW"}
You would use 1 stroke for each of the first 3 lines, and then 3 strokes on the last line.



This wouldn't be an issue if we had forever to paint the picture. Unfortunately, you only have enough time to make at most maxStrokes distinct strokes. Any more strokes would put you past your deadline. Since finishing on time is more important than getting it perfect, you are willing to mispaint some of the spaces. Return the fewest number of spaces that can be mispainted while still using no more than maxStrokes strokes. An unpainted space is considered mispainted.
 

Definition

    
Class:MiniPaint
Method:leastBad
Parameters:String[], int
Returns:int
Method signature:int leastBad(String[] picture, int maxStrokes)
(be sure your method is public)
    
 

Constraints

-picture will contain between 1 and 50 elements inclusive.
-Each element of picture will contain between 1 and 50 characters inclusive.
-Each element of picture will contain the same number of characters.
-Each character in each element of picture will be (quotes for clarity) 'B' or 'W'.
-maxStrokes will be between 0 and 3000 inclusive.
 

Examples

0)
    
{
"BBBBBBBBBBBBBBB",
"WWWWWWWWWWWWWWW",
"WWWWWWWWWWWWWWW",
"WWWWWBBBBBWWWWW"}
6
Returns: 0
Exactly enough strokes to finish the job.
1)
    
{
"BBBBBBBBBBBBBBB",
"WWWWWWWWWWWWWWW",
"WWWWWWWWWWWWWWW",
"WWWWWBBBBBWWWWW"}
4
Returns: 5
One stroke for each row produces the least problem.
2)
    
{
"BBBBBBBBBBBBBBB",
"WWWWWWWWWWWWWWW",
"WWWWWWWWWWWWWWW",
"WWWWWBBBBBWWWWW"}
0
Returns: 60
Now the entire picture will be mispainted.
3)
    
{
"BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW",
"BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW",
"BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW",
"BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW",
"BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW",
"BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW"}
100
Returns: 40
This one needs a lot of strokes.
4)
    
{"B"}
1
Returns: 0

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=1996

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4710&pm=1996

Writer:

brett1479

Testers:

lbackstrom , schveiguy

Problem categories:

Dynamic Programming