Leetcode.com problem 1473: "Paint-House-III"

James S. Plank

Sun Jul 10 11:30:00 EDT 2022

Problem Statement.
A skeleton with a main() that reads problems from stdin. The format is different from the method. It goes m, n, target, and then houses and cost.
A program that generates input problems (although it doesn't verify that solutions are possible).
Solution.cpp -- A commented solution.
Enum.cpp -- A solution that uses enumeration. This is not fast enough for the Leetcode parameters, but I used it to verify my program on smaller inputs.
tests.sh -- Testing script.
answers.txt -- Correct output of the testing script.
Success Rate (as of July, 2022): 62.2%

In case Leetcode's servers are down

If Leetcode's servers are down, I've given you tools to do the problem anyway. Do the solution in main.cpp, and then you can test yourself with tests.sh. Your output should match answers.txt, and your timing should be roughly the same as mine, which was just under 2 seconds.

Here is a summary of the problem:

There are m houses. Each is either unpainted, or painted a specific color.
There are n colors, which are simply the numbers from 1 to n.
You are given a vector houses, which contains numbers from 0 to n. If house i is unpainted, then houses[i] is 0. Otherwise houses[i] is the color of house i.
You are given a two dimensional matrix cost. The value in cost[i][j] is the cost of painting house i so that its color is j+1. It's j+1, because color "0" means "unpainted".
Your goal is to paint the unpainted houses in the cheapest manner possible. When you are done, there should be exactly target groups of adjacent houses, where each group is the same color, and adjecent groups are painted different colors.
Return this cost, or -1 if you can't achieve the target.

The examples

The format here is M, N, Target, then Houses, then Costs

Problems/input-1.txt
5 2 3
0 0 0 0 0
1 10  10 1  10 1  1 10  5 1

Answer = 9 -- Paint them 1, 2, 2, 1, 1.

Problems/input-2.txt
5 2 3
0 2 1 2 0
1 10  10 1  10 1  1 10  5 1

Answer = 11 -- Paint them 2, 2, 1, 2, 2

Problems/input-3.txt
4 3 3
3 1 2 3
1 1 1 
1 1 1 
1 1 1 
1 1 1 

Answer = -1.  Can't be done.

I have 100 more problems in Problems/??.txt. That's what tests.txt runs.

Hints

This is a dynamic program, plain and simple. I'm guessing that the success rate is high, because more experienced programmers take on the "hard" problems, and experienced programmers are used to dynamic programming.

As always, the challenge is to spot the recursion. This is a pretty typical recursion for a DP problem: Call DP(i), where you know that all houses with numbers less then i are painted. Then, in DP(), you try all possible colors, and return the minimum.

It's a little more complex than that though. My recursive procedure was DP(index, target, prev), where:

index means all houses with numbers less than that have been painted.
target is the number of new groups that you want to create, starting with the house with number index.
prev is the color of houses[index-1].

DP() returns the minimum cost of painting the houses starting with index. You start with DP(0, target, -1).

Let's do example 2.

DP(0, 3, -1) makes two recursive calls:
  - Paint house 0 color 1: Cost =  1 plus DP(1, 2, 1).
  - Paint house 0 color 2: Cost = 10 plus DP(1, 2, 2).
  Let's walk through the recursions:

  DP(1, 2, 1) means house[0] is color 1.  Since house 1 is painted with color 2, that means
     you have to start a new group with house 1 and you only make one recursive call.
     That is: DP(2, 1, 2).

    DP(2, 1, 2) means house[1] is color 2.  Since house 2 is painted with color 1, that means
       you have to start a new group with house 2 and you only make one recursive call.
       That is: DP(3, 0, 1).

      DP(3, 0, 1) means house[2] is color 1.  Since house 3 is painted with color 2, that means
         you have to start a new group with house 3, and that would set target to -1.  That means
         it's impossible, so DP(3, 0, 1) returns -1.

    DP(2, 1, 2) returns -1 too.
 DP(1, 2, 1) returns -1 too.

So now we're back in DP(0, 3, -1), which is now going to call DP(1, 2, 2).

  DP(1, 2, 2) means house[0] is color 2.  Since house 1 is also color 2, you make
     the recursive call: DP(2, 2, 2).

    DP(2, 2, 2) means house[1] is color 2.  House[2] is color 1, so we call DP(3, 1, 1).

      DP(3, 1, 1) means house[2] is color 1.  House[3] is color 2, so we call DP(4, 0, 2);

        DP(4, 0, 2) means house[3] is color 1.  House[4] is unpainted, so we can do two things:

          - Paint it 1: which would call DP(5, -1, 1).  That call is illegal, so we don't do it.
          - Paint it 2: which calls DP(5, 0, 2), and adds 1 to the answer.

          DP(5, 0, 2) -- we're in the base case: return 0.

        So DP(4, 0, 2) returns 1.
      DP(3, 1, 1) returns 1.
    DP(2, 2, 2) returns 1.
  DP(1, 2, 2) returns 1.

So now we're back in DP(0, 3, -1) and our answer is 10 plus DP(1, 2, 2), which is 11.

Your memoization cache stores the three variables. I made my a vector of vector of vectors of ints, whose size is O(m * target * n). You can use that as the running time of the program, too.

Some pitfalls, testing, improving

There are some pitfalls in this program. The major one is the fact that costs[i][j] stores the cost of painting house i with color j+1. An easy way to fix that is to run through houses and decrement each house by one. Now "-1" means unpainted.

The other pitfall is to only use the leetcode examples for testing. I know we all want to submit as quickly as possible, but you should test. Basically, your program is going to have a bunch of conditions, and you should concoct an example that tests every single one of those before you submit. I know it's no fun, but that's better than not testing and finding a bug in the condition that you didn't test. It happened to me.

You can of course make this faster by, for example, shrinking houses by condensing groups of consecutive painted houses. I didn't do that, BTW, but it would work. It can also shrink the size of your memoization cache.