9 weeks ago

John 910

Hyderabad

Avg CTC: 18lpa

Job Roles Available: Software Engineer, SE-Test and other roles

Application Link: Job List

Question

Number of ways to arrange balloons

Your friend's birthday is nearby. He asked you to take care of balloon decoration. He has bought White and Yellow balloons of N and M quantities respectively. You have to decorate the balloons by placing the balloons in a straight line in any order. He likes a decoration when there are no more than W white balloons placed successively or there are no more than Y yellow balloons placed successively.

Your friend wants to know the number of decorations that are possible from given input such that he likes the decorations.

Note: A line filled with balloons in any order is considered as a decoration.

Input:

The first and the only line contains four space separated integers N, M, W, Y

Constraints

• 1 <= N, M <= 100
• 1 <= W,Y <=10

Output:

Print the number of decorations your friend will like modulo 100000000

Test case 1

2 1 1 10

Output:

1

Explanation

Only possible way to arrange is 'white, yellow, white'

Note: 'white, white, yellow' or 'yellow, white, white' not possible because we cannot have more than 1 white.

Test case 2

2 3 1 2

Output:

5

21 months ago

Yash Sahijwani 940

Solution for Number of ways to arrange balloons

Analysis

In the question, it is mentioned that we have N white balloons, and M yellow balloons which need to be arranged in a line such that there are not more than W consecutive white balloons and not more than Y consecutive yellow balloons.

Method 1: Brute Force

A naive method would be to generate all possible permutations of the balloons, and then check for each permutation whether it is a valid permutation or not. Since, all white balloons are considered as same and all yellow balloons are considered as same, the number of permutations will basically be the number of ways in which we can select the positions where the white balloons will be. So, out of a total n+m positions, we need to select n positions for the white balloons, so total possible number of ways will be n+m choose n. Also, checking each permutation, whether is valid or not will take O(m+n) time. Now, given the constraints, n+m can go till 200, and n+m choose n will be maximized at n=100, m=100. So at that point n+m choose n will be greater than 2^100. So overall, this will take a large amount of time and will give Time Limit Exceeded verdict even though the constraints are small.

Method 2: Dynamic Programming

We can approach this problem using Dynamic Programming, since the constraints are small. We define the state as:

(current_index,
number_of_white_balloons_used,
previous_balloon_type,
number of consecutive balloons before current_index)

So, say we are at the index current_index and we need to decide which type of balloon to place. In order to decide, we need to know a few things:

1. How many white balloons and how many yellow balloons are remaining, because we can only use them if there current freq is not 0.
2. Previous balloon used at current_index - 1 and the number of consecutive balloons of the same type just before current_index, because we need to keep in mind the condition of not more than W consecutive white balloons, and not more than Y consecutive yellow balloons.

The transition for this DP will be as follows: (have abbreviated the state variables)

If we still have white balloons which we can choose (N - white should be greater than 0), and the previous balloon is yellow:

dp[curr][white][prev][prev_freq] += (dp[curr+1][white+1][1][1]) // here the 1 at the 3rd variable (previous balloon type) signifies a white balloon

If we still have white balloons which we can choose (N - white should be greater than 0), and the previous balloon is white but the prev_freq < = W:

dp[curr][white][prev][prev_freq] += (dp[curr+1][white+1][1][prev_freq+1]

If we still have yellow balloons which we can choose, and the previous balloon is white:

dp[curr][white][prev][prev_freq] += (dp[curr+1][white][2][1])

If we still have yellow balloons which we can choose, and the previous balloon is yellow, but the prev_freq < = Y:

dp[curr][white][prev][prev_freq] += (dp[curr+1][white][2][prev_freq+1]

Now, each transition takes constant time, so the only time complexity will be due to the state, which will be O(200 * 100 * 2 * 10) = O(4 x 10^5)

Implementation

Note: Here I have used the iterative form of DP, you can also try with recursive DP which is a bit easier to code but takes more time due to recursion stack. (Both of them will work)

for(ll i=0;i < = n;i++)
    for(ll j=0;j < 3;j++)
        for(ll k=0;k < = max_freq;k++)
            dp[tot][i][j][k] = 1;
for(ll i=tot-1;i > = 0;i--)
{
    // i = curr_index
    for(ll j=min(n, i);j > = 0;j--)
    {
        // j = number of whites used
        for(ll k=2;k > = 1;k--)
        {

            if(k==1)
            { 
                // previous is white
                for(ll u=w;u > = 0;u--)
                {
                    ll rem_white = n - j;
                    ll rem_yellow = m - (i-j);
                    if(rem_yellow < 0 || rem_white < 0)
                        continue;
                    if(rem_yellow==0 && rem_white==0)
                        continue;
                    if(rem_yellow==0)
                    {
                        if(u==w) //already white prev freq is w
                            continue;
                        //previously white, now use another white
                        dp[i][j][k][u] = (dp[i][j][k][u]%mod + dp[i+1][j+1][1][u+1]%mod)%mod;
                    }
                    else if(rem_white==0)
                    {
                        //previous white, now use yellow
                        dp[i][j][k][u] = (dp[i][j][k][u]%mod + dp[i+1][j][2][1]%mod)%mod;
                    }
                    else
                    {
                        //use white
                        if(u!=w)
                            dp[i][j][k][u] = (dp[i][j][k][u]%mod + dp[i+1][j+1][1][u+1]%mod)%mod;
                        //use yellow
                        dp[i][j][k][u] = (dp[i][j][k][u]%mod + dp[i+1][j][2][1]%mod)%mod;
                    } 
                }
            }
            else if(k==2)
            {
                //previous is yellow
                for(ll u=y;u > = 0;u--)
                {
                    ll rem_white = n - j;
                    ll rem_yellow = m - (i-j);
                    if(rem_yellow < 0 || rem_white < 0)
                        continue;
                    if(rem_yellow==0 && rem_white==0)
                        continue;
                    if(rem_white==0)
                    {
                        if(u==y) //already yellow prev freq is y
                            continue;
                        //previously yellow, now use another yellow
                        dp[i][j][k][u] = (dp[i][j][k][u]%mod + dp[i+1][j][2][u+1]%mod)%mod;
                    }
                    else if(rem_yellow==0)
                    {
                        //previous yellow, now use white
                        dp[i][j][k][u] = (dp[i][j][k][u]%mod + dp[i+1][j+1][1][1]%mod)%mod;
                    }
                    else
                    {
                        //use yellow
                        if(u!=y)
                            dp[i][j][k][u] = (dp[i][j][k][u]%mod + dp[i+1][j][2][u+1]%mod)%mod;
                        //use white
                        dp[i][j][k][u] = (dp[i][j][k][u]%mod + dp[i+1][j+1][1][1]%mod)%mod;
                    } 
                }
            }
        }
    }
}
ll ans = (dp[0][0][1][0]);

14 months ago

vikky anand • 0

Easy solution 
recursion + memoisation

#include<bits/stdc++.h>

using namespace std;

#define int long long

#define all(x) begin(x),end(x)

int n,m,w,y;

int dp[101][101][11][11];

int mod=1e9+7;

int f(int i,int j,int nw,int ny){

if(i>n||j>m) return 0;

if(i==n&&j==m) return 1;

if(dp[i][j][nw][ny]!=-1) return dp[i][j][nw][ny];

if(nw==w)  return dp[i][j][nw][ny]=f(i,j+1,0,ny+1);

if(ny==y)  return dp[i][j][nw][ny]=f(i+1,j,nw+1,0);

return dp[i][j][nw][ny]=(f(i+1,j,nw+1,0)+f(i,j+1,0,ny+1))%mod;

}

void solve(){

cin>>n>>m>>w>>y;

memset(dp,-1,sizeof(dp));

cout<<f(0,0,0,0);

}

int32_t main(){

solve();

return 0;

}