Beautiful City

Hard
0/120
Average time to solve is 40m
profile
Contributed by
1 upvote
Asked in company
Sopra Steria

Problem statement

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?

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
3 2 1 1 5
7 2 5 1 1
Sample Output 1:
1
0
Explanation for Sample Input 1:
In the first test case, the only way to colour is red, blue, red.
In the second test case, we have 2 buckets of red and 5 buckets of blue. Hence, there is no possible way in which no two consecutive houses are painted blue.
Sample Input 2:
2
5 1 4 1 1
2 1 1 4 5
Sample Output 2:
0 
2
Hint

Can we check all possible combinations of colouring the houses and count the beautiful ones?

Approaches (2)
Brute Force

 

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.

  1. 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).
  2. 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’
Time Complexity

O(2 ^ N), where ‘N’ is the total number of houses.


 

For each index, we are finding the number of ways to place both red and blue. So total time complexity becomes O(2 ^ N).


 

Space Complexity

O(2 ^ N), where ‘N’ is the total number of houses.


 

Since we are going to call the recursive function at most 2 ^ ‘N’ times which will occupy space in the stack.So total space complexity becomes O(2 ^ N).


 

Code Solution
(100% EXP penalty)
Beautiful City
Full screen
Console