TopCoder MiniPaint – SRM 178 Div 1

https://community.topcoder.com/stat?c=problem_statement&pm=1996&rd=4710

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 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)2010, TopCoder, Inc. All rights reserved.

http://acmph.blogspot.com/2018/02/topcoder-srm-178-div-1-minipaint.html

First of all it must be clear that having a fixed number of strokes for each row, the problem can be solved independently for each row, so on a top level we have to decide how many strokes to assign to each row and tell them to solve themselves (paint themselves) and then we choose the best combination. So in order to solve the assignment problem we use dynamic programming.
  
    int g(int row, int strokes)

This is the state of our outer DP, which tells if we have to solve rows in range [0...row] and only have strokes number of strokes left, what would be the minimum number of mispainted cells? So we can assign 0, 1, 2, ..., width assigns to the current row and solve g(row-1, strokes-k) which k is the number of strokes that we have assigned to the current row, in this case what would be the number of mispainted cells for this row? f(row, length-1, k) but what this means?

     int f(int row, int idx, int strokes)

This is the state of our inner DP, which means we want to paint row of the picture in range [0...idx] and only have strokes number of strokes left. There are two options for us, first not paint cell at (row, idx), which means cost off(row, idx-1, strokes-1) + 1, or paint cells in range [k...idx] with cost of f(row, k-1, strokes-1) + numberOfCellsDifferent to cell at (row, idx).

Think about base cases yourself. (e.g. where row is -1 or strokes is equal to zero)

https://github.com/darkzeroman/topcoder/blob/master/minipaint-java/MiniPaint.java
https://github.com/gabesoft/topc/blob/master/src.archive.1/dynamic/MiniPaint.java