Last Updated: 28 Oct, 2021
Beautiful City
Hard
Asked in company
The new mayor of your city has appointed you to paint the houses of your city to make the city look beautiful. The city consists of ‘N’ houses arranged in a straight line.
The mayor has provided you with ‘R’ buckets of red paint and ‘B’ buckets of blue paint (R + B = N). And you need exactly 1 bucket to paint 1 house.
The mayor considers the city beautiful if no more than ‘X’ consecutive houses are painted red, and no more than ‘Y’ consecutive houses are painted blue.
Apart from being a painter, you are also a good mathematician. Hence, you wonder how many ways you could paint the houses such that the city looks beautiful. Can you find the answer modulo 10^8?
Input Format:
The first line of input contains an integer ‘T’, denoting the number of test cases.
The first line of each test case contains five space-separated integers,’N’, ‘R’, ‘B’, ‘X’ and ’Y’ denoting the total number of houses, number of red paint buckets, number of blue paint buckets, maximum number of consecutive houses that can be painted red and maximum number of consecutive houses that can be painted blue.
Output Format:
For each test case, print a single integer denoting the number of ways you can paint the houses modulo (10^8).
Note:
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 10
2 <= N <= 200
1 <= R, B <= 100
1 <= X, Y <= 10
Time Limit: 1 sec
Approaches
We need to count all the possible combinations of colouring the houses such that no more than ‘X’ consecutive houses are painted red, and no more than ‘Y’ consecutive houses are painted blue.
We will be calculating this recursively.
Let F(p,q,t,s) denote the number of ways to colour ‘p’ + ‘q’ number of houses such that exactly ‘p’ number of houses are coloured red, exactly ‘q’ number of houses are coloured blue. Such that the next ‘t’ number of houses will strictly be red and next ‘s’ number of houses will strictly be blue. As we know, a house can only be coloured either red or blue, so either ‘t’ or ‘s’ will be 0.
For example :
In the above example F(3, 1, 2, 0) represents the number of ways to colour houses from 1 to 4 such that exactly 3 houses have colour red, 1 house has colour blue, and next 2 houses, i.e. houses from 5 to 6 are coloured red, and next 0 houses are coloured blue.
Few points to note :
- The number of ways to arrange 0 red and 0 blue houses is 1, which will be our base case.
- If ‘t’ > ‘X’, i.e. the number of consecutive red houses is greater than ‘X’, then the city will not be beautiful, so the number of ways to arrange this will be 0.
- If ‘s’ > ‘Y’, i.e. the number of consecutive blue houses is greater than ‘Y’, then the city will not be beautiful, so the number of ways to arrange this will be 0.
- As the number of houses can not be negative, if ‘p’ or ‘q’ is the negative number of ways to arrange, that will be 0.
After considering all the above points, we will have two options: place red at the end or blue at the end.
- If we place red at the end, the number of houses to be coloured red will decrease by 1, and the number of consecutive houses having the colour red will increase by 1. So the number of ways becomes F(p - 1, q, t + 1, 0).
- If we place blue at the end, the number of houses to be coloured blue will decrease by 1, and the number of consecutive houses having the colour blue will increase by 1. So the number of ways becomes F(p, q - 1, 0, s + 1).
Combining these two we get :
F(p, q, t, s) = F(p - 1, q, t + 1, 0) + F(p, q - 1, 0 , s + 1)
Our final aim is to find the number of ways to arrange all the ‘N’ houses using ‘R’ red hoses, ‘B’ blue houses such that the next 0 houses have the colour red or blue. So the final answer is going to be :
F(R, B, 0, 0)
Algorithm:
- Create a function with four parameters F(p, q, t, s).
- If ‘p’ is less than 0 or ‘q’ is less than 0, return 0.
- If ‘t’ > ‘X’ or ‘s’ > ‘Y’ return 0.
- If p is equal to 0 and q is equal to 0, return 1.
- Else return sum of F(p - 1, q, t + 1, 0) and F(p, q - 1, 0 , s + 1) modulo (10^8).
- Initialise ‘ans’ to F(R, B, 0, 0)
- Return ‘ans’
Notice that we will end up calling the function with the same values multiple times, for which we will end up recalculating the value which we already calculated.
Thus, there will be many overlapping subproblems in the recursive approach. This can be solved using the memoization technique.
We will use an array ‘dp’ to store an already visited state, and once we reach that state again, instead of recalculating its value, we will directly return the value we stored in the array ‘dp’.
Algorithm:
- Create a 4d array ‘dp’ of size (R + 1) * (B + 1) * 11 * 11 and initialise it with -1.
- Create a function with four parameters F(p, q, t, s).
- If ‘p’ is less than 0 or ‘q’ is less than 0, return 0.
- If ‘t’ > ‘X’ or ‘s’ > ‘Y’ return 0.
- If p is equal to 0 and q is equal to 0, return 1.
- If ‘dp[p][q][t][s]’ is not equal to -1, return ‘dp[p][q][t][s]’.
- Else update ‘dp[p][q][t][s]’ to sum of F(p - 1, q, t + 1, 0) and F(p, q - 1, 0 , s + 1) modulo (10^8).
- Return ‘dp[p][q][t][s]’
- Initialise ‘ans’ to F(R, B, 0, 0)
- Return ‘ans’