CODEWITHSUNDEEP
recursionmathdynamic
Minh Hien
Minh Hien

Reputation: 263

The game with the marbles

Problem: There are R red marbles, G green marbles and B blue marbles (R≤G≤B) Count the number of ways to arrange them in a straight line so that the two marbles next to each other are of different colors.

For example, R=G=B=2, the answer is 30.

I have tried using recursion and of course TLE:

Define r(R,B,G) to be the number of ways of arranging them where the first marble is red. Define b(R,B,G),g(R,B,G) respectively.
Then r(R, B, G) = b(R-1,B,G) + g(R-1,B,G)
And the answer is r(R,B,G) + b(R,B,G) + g(R,B,G)

But we can see that r(R, B, G) = b(B, R, G) ...
So, we just need a function f(x,y,z)=f(y,x−1,z)+f(z,x−1,y)
And the answer is f(x,y,z) + f(y,z,x) + f(z,x,y).

The time limit is 2 seconds.

I don't think dynamic is not TLE because R, G, B <= 2e5

Upvotes: 1

Views: 266

Answers (2)

r3mainer
r3mainer

Reputation: 24567

You can use symmetry to cut down the number of recursions.

For example, if (R, G, B) = (30, 20, 10) and the last marble was red, the number of permutations from this position is exactly the same as if the last marble was blue and (R, G, B) = (10, 20, 30).

Given that R ≤ G ≤ B is set as a starting condition, I would suggest keeping this relationship true by swapping the three values when necessary.

Here's some Python code I came up with:

memo = {}
def marble_seq(r, g, b, last):
    # last = colour of last marble placed (-1:nothing, 0:red, 1:green, 2:blue)
    if r == g == b == 0:
        # All the marbles have been placed, so we found a solution
        return 1
    # Enforce r <= g <= b
    if r > g:
        r, g = g, r
        last = (0x201 >> last * 4) & 0x0f  # [1, 0, 2][last]
    if r > b:
        r, b = b, r
        last = (0x012 >> last * 4) & 0x0f  # [2, 1, 0][last]
    if g > b:
        g, b = b, g
        last = (0x120 >> last * 4) & 0x0f  # [0, 2, 1][last]
    # Abort if there are too many marbles of one colour
    if b>r+g+1:
        return 0
    # Fetch value from memo if available
    if (r,g,b,last) in memo:
        return memo[(r,g,b,last)]
    # Otherwise check remaining permutations by recursion
    result = 0
    if last != 0 and r > 0:
        result += marble_seq(r-1,g,b,0)
    if last != 1 and g > 0:
        result += marble_seq(r,g-1,b,1)
    if last != 2 and b > 0:
        result += marble_seq(r,g,b-1,2)
    memo[(r,g,b,last)] = result
    return result

marble_seq(50,60,70,-1)  # Call with `last` set to -1 initially

(Result: 205435997562313431685415150793926465693838980981664)

This probably still won't work fast enough for values up to 2×105, but even with values in the hundreds, the results are quite enormous. Are you sure you stated the problem correctly? Perhaps you're supposed to give the results modulo some prime number?

Upvotes: 1

Scott Hunter
Scott Hunter

Reputation: 49813

Some things to limit the recursion:

  • If R>G+B+1, then there is no way to avoid having 2 adjacent reds. (Similar argument for G>R+B+1 & B>R+G+1.)
  • If R=G+B+1, then you alternate reds with non-reds, and your problem is reduced to how many ways you can arrange G greens and B blacks w/o worrying about adjacency (and should thus have a closed-form solution). (Again, similar argument for G=R+B+1 and B=R+G+1.)

Upvotes: 1

Related Questions