MiniPaint | Topcoder Archive

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

{
"BBBBBBBBBBBBBBB",
"WWWWWWWWWWWWWWW",
"WWWWWWWWWWWWWWW",
"WWWWWBBBBBWWWWW"}

Returns: 0

Exactly enough strokes to finish the job.

{
"BBBBBBBBBBBBBBB",
"WWWWWWWWWWWWWWW",
"WWWWWWWWWWWWWWW",
"WWWWWBBBBBWWWWW"}

Returns: 5

One stroke for each row produces the least problem.

{
"BBBBBBBBBBBBBBB",
"WWWWWWWWWWWWWWW",
"WWWWWWWWWWWWWWW",
"WWWWWBBBBBWWWWW"}

Returns: 60

Now the entire picture will be mispainted.

{
"BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW",
"BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW",
"BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW",
"BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW",
"BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW",
"BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW"}

Returns: 40

This one needs a lot of strokes.

```
{"B"}
```
```
1
```
```
Returns: 0
```

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.