CODEWITHSUNDEEP
algorithm
driftdrift
driftdrift

Reputation: 339

How do I approach this Combinatorics Fence-Paint algorithm?

I'm stuck on this question on lintcode, and I've read two past solutions but neither of them make sense to me.

The question is as following:

There is a fence with n posts, each post can be painted with one of the k colors.
You have to paint all the posts such that no more than two adjacent fence posts have the same color.
Return the total number of ways you can paint the fence.

Given n =3, k=2, return 6.

So the part I do understand is that if n=0 (we have 0 posts) or k = 0(we have 0 paints), we can't paint anything so return 0

And if n == 1, the post can be painted in K ways so return k

When n is 2, we can paint it in K*1 ways if adjacent posts are equal and K*(K-1) ways if adjacent posts are different.

if n ==3 or more: Same adjacent colors would be: K * 1 * K-1 * 1 * K-1... And different would be: K * K-1 * K-1 ....

How do I proceed from here? I've seen one guy create a matrix with [0, k, 2k, and 0] again and another guy simplify the "different colors" to (k+k*(k-1)) * (k-1) but I don't know how either of them jump to that step of their conclusion

edit: One guys solution is the following:

class Solution:
# @param {int} n non-negative integer, n posts
# @param {int} k non-negative integer, k colors
# @return {int} an integer, the total number of ways
def numWays(self, n, k):
    # Write your code here
    table = [0, k, k*k, 0]

    if n <= 2:
        return table[n]

    # recurrence equation
    # table[posts] = (color - 1) * (table[posts - 1] + table[posts - 2])
    for i in range(3, n + 1):
        table[3] = (k - 1) * (table[1] + table[2])
        table[1], table[2] = table[2], table[3]

    return table[3]

but I cant understand how why he has [0] at the end of his table, and how he set up the recurrence equation

Upvotes: 1

Views: 715

Answers (2)

Gribouillis
Gribouillis

Reputation: 2220

Following Dominik G's answer, one can give an explicit formula for L(n,k) because for fixed k it is a constant recursive sequence

My result is that for k >= 2, if D = sqrt((k+1)^2 - 4) and u = (k-1+D)/2 and v = (k-1-D)/2 are the two solutions of the quadratic equation x^2 = (k-1)(x + 1), then one has for n >= 1

L(n, k) = (k/(k-1))*((u^(n+1)-v^(n+1))/D

This makes a fast algorithm if one can compute with sufficient floating point precision.

Hmm, I'm afraid latex formatting doesn't work here, but the formulas are easy to understand

Upvotes: 0

Dominik G
Dominik G

Reputation: 614

Most difficult part of this problem is setting up recursion. Let L be the function returning number of combinations given n posts and k colors. Then there are two cases to consider:

a. Adding two posts in same color:

L(n+2,k) = (k-1)*L(n,k)

b. Adding two posts in different colors:

L(n+1,k) = (k-1)*L(n,k)

which gives forumula:

L(n,k) = (k-1)*(L(n-1,k)+L(n-2,k))

Example

For n=3 and k=2, lets say we know the number of combinations with first two posts which are

n=1 | k = 2

n=2 | k*k = 4

Now the to solve for n=3 we need to use previuosly calculated values having adjacent n=2 and n=3

a. Different colors: by adding one post different than the trailing one, sum[2]*(k-1) = 4

b. Same color: stepping back one tile and adding two in the same color other than n=1, which gives sum[1]*(k-1) = 2

As for matrix its a matter of taste, vars like current and prev would be fine as well.

Upvotes: 1

Related Questions