sahilshelangia's blog

count no. of ways.
By sahilshelangia, history, 6 years ago, In English

we are given N red balls and M blue balls, we have to find no. of arrangements of (n+m) balls such that no more than k consecutive balls are of the same color.

1<n,m,k<=1000

  • Vote: I like it
  • +14
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
6 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sahilshelangia (previous revision, new revision, compare).

→ Reply
»
6 years ago, hide # |
← Rev. 4  
Vote: I like it +13 Vote: I do not like it
Solution
→ Reply
  • »
    »
    6 years ago, hide # ^ |
     
    Vote: I like it +11 Vote: I do not like it

    dp[i][j][0]=dp[i−1][j][0]+dp[i−1][j][1]-dp[i−k][j][1]
    dp[i][j][1]=dp[i][j−1][0]+dp[i][j−1][1]-dp[i][j−k][0]


    the last term in both the cases should be subtracted?

    → Reply
    • »
      »
      »
      6 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Of course, fixed

      → Reply
      • »
        »
        »
        »
        6 years ago, hide # ^ |
        ← Rev. 3  
        Vote: I like it -8 Vote: I do not like it

        I am getting twice the actual answer. Here is the code. Your solution seems wrong.


        #include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define int long long
#define double long double

int32_t main()
{
    IOS
    int n,m,k;
    cin>>n>>m>>k;
    int dp[n+5][m+5][2]={};
    dp[0][0][0]=1;
    dp[0][0][1]=1;
    for(int red=0;red<=n;red++)
        for(int blue=0;blue<=m;blue++)
            if(red+blue)
            {
                dp[red][blue][0]+= red!=0?(dp[red-1][blue][0]+dp[red-1][blue][1]):0;
                    dp[red][blue][1]+= blue!=0?(dp[red][blue-1][0]+dp[red][blue-1][1]):0;
                if(red-k>=1)
                    dp[red][blue][0]-=dp[red-k][blue][1];
                if(blue-k>=1)
                    dp[red][blue][1]-=dp[red][blue-k][0];
            }

    cout<<dp[n][m][0]+dp[n][m][1];
}
        → Reply
        • »
          »
          »
          »
          »
          6 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          Probably my base cases are wrong. Check with $$$dp[1][0][0] = 1, dp[0][1][1] = 1$$$

          → Reply
        • »
          »
          »
          »
          »
          6 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          yes, it would give you a wrong answer,
          In do transition we should consider

          dp[i][j][0]=dp[i−1][j][0]+dp[i−1][j][1]-dp[i−k][j][1]


          The last term should be dp[i-k-1][j][1].
          as we have to find no. of ways in which no more than k elements of the same color. But we are allowing k consecutive color.

          → Reply
        • »
          »
          »
          »
          »
          6 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it 
          #include<bits/stdc++.h>
#define ll long long int
const ll MOD=1e9+7;
using namespace std;
ll dp[1005][1005][2];
ll solve(int n,int m,int k,int endingWith){
	if(n<0||m<0)
		return 0;
	if(n==0&&m==1){
		return endingWith==1;
	}
	if(n==1&&m==0){
		return endingWith==0;
	}
	if(n==0&&m==0)
		return 1;

	ll &ans=dp[n][m][k];
	if(ans!=-1)
		return ans;
	if(endingWith==0)
		ans=solve(n-1,m,k,0)+solve(n-1,m,k,1)-solve(n-k-1,m,k,1);
	
	else
		ans=solve(n,m-1,k,0)+solve(n,m-1,k,1)-solve(n,m-k-1,k,0);

	ans=ans%MOD;
	return ans;
}
int main()
{
	int t;
	cin>>t;
	while(t--){
		memset(dp,-1,sizeof(dp));
		int n,m,k;
		cin>>n>>m>>k;
		ll ans=solve(n,m,k,1)+solve(n,m,k,0);
		ans=ans%MOD;
		cout<<ans<<endl;
	}	
	return 0;
}
          → Reply
  • »
    »
    6 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    I think the recurrence relations should be

    dp[i][j][0]=dp[i−1][j][0]+dp[i−1][j][1]−dp[i−k][j][0]
dp[i][j][1]=dp[i][j−1][0]+dp[i][j−1][1]−dp[i][j−k][1]

    because we should subtract cases which have more than k consecutive red/blue balls.

    Also, I think initialization is wrong here. using dp[0][0][0]=dp[0][0][1]=1, we get dp[0][1][1]=2 for k>1, which is obviously wrong.

    I think it should be

    for(int i=0;i<=k;i++)dp[0][i][1]=1,dp[i][0][0]=1;

    where dp is computed from 1..n and 1..m

    → Reply
»
6 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Deleted.

→ Reply