MiniPaint
SRM 178 · 2004-01-07 · by brett1479
SRM 178 · 2004-01-07 · by brett1479 · Dynamic Programming
Problem Statement
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:
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.
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.
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
Submissions are judged against all 88 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class MiniPaint with a public method int leastBad(vector<string> picture, int maxStrokes) · 88 test cases · 2 s / 256 MB per case