There are p balls of type P, q balls of type Q and r balls of type R. Using the balls we want to create a straight line such that no two balls of same type are adjacent.
 
Example 1:
Input: p = 2, q = 2, r = 2
Output: 30
Explanation: There are 30 possible arrangements
of balls. Some of them are PQR, PRQ, PRP, PRQ,
PQR,...
Example 2:
Input: p = 1, q = 1, r = 1
Output: 6
Explanation: There are 6 possible arrangements
and these are PQR, PRQ, QPR, QRP, RPQ, RQP.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function CountWays() which takes count of P type balls, Q type balls and R type balls and returns total number of possible arrangements such that no two balls of same type are adjacent modulo 10^{9} + 7.
 
Expected Time Complexity: O(N^{3}) where N = max(p, q, r)
Expected Space Complexity: O(N^{3})
 
Constranits: 
1 <= p, q, r <= 100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Combinatorics

Mathematics

Starter code: #User function Template for python3



class Solution:

	def CountWays(self, p, q, r):

		# Code here

Solutions:
MAX = 101
dp = [[[[-1] * 4 for i in range(MAX)] for j in range(MAX)] for k in range(MAX)]

def countWayss(p, q, r, last):
	if p < 0 or q < 0 or r < 0:
		return 0
	if p == 1 and q == 0 and (r == 0) and (last == 0):
		return 1
	if p == 0 and q == 1 and (r == 0) and (last == 1):
		return 1
	if p == 0 and q == 0 and (r == 1) and (last == 2):
		return 1
	if dp[p][q][r][last] != -1:
		return dp[p][q][r][last]
	if last == 0:
		dp[p][q][r][last] = countWayss(p - 1, q, r, 1) + countWayss(p - 1, q, r, 2)
	elif last == 1:
		dp[p][q][r][last] = countWayss(p, q - 1, r, 0) + countWayss(p, q - 1, r, 2)
	else:
		dp[p][q][r][last] = countWayss(p, q, r - 1, 0) + countWayss(p, q, r - 1, 1)
	return dp[p][q][r][last]

def countUtil(p, q, r):
	return countWayss(p, q, r, 0) + countWayss(p, q, r, 1) + countWayss(p, q, r, 2)

class Solution:

	def CountWays(self, p, q, r):
		return countUtil(p, q, r) % int(1000000000.0 + 7)