### sahilshelangia's blog

By sahilshelangia, history, 4 years ago,

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

• +14

| Write comment?
 » 4 years ago, # |   0 Auto comment: topic has been updated by sahilshelangia (previous revision, new revision, compare).
 » 4 years ago, # | ← Rev. 4 →   +13 Solution$dp[i][j][c]$ is the number of ways to distribute $i$ red balls and $j$ blue balls with the last ball of color $c$ ($0$ = red, $1$ = blue)to calculate $dp[i][j][0]$ - the total configurations are $dp[i - 1][j][0] + dp[i - 1][j][1]$ (configurations with $i - 1$ red balls and $j$ blue balls) - you have to subtract the configurations with $k - 1$ red balls at the end (because you can't add another red ball). Moreover, you know that the ball before the $k - 1$ red balls must be blue. So you have to subtract $dp[i - k][j][1]$$dp[i][j][1]$ can be calculated similarlyso $dp[1][0][0] = dp[0][1][1] = 1$ $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]$ (if some index is $< 0$, assume that the value of dp is $0$)hope this is correct
•  » » 4 years ago, # ^ |   +11 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?
•  » » » 4 years ago, # ^ |   0 Of course, fixed
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   -8 I am getting twice the actual answer. Here is the code. Your solution seems wrong. #include 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<
•  » » » » » 4 years ago, # ^ |   0 Probably my base cases are wrong. Check with $dp[1][0][0] = 1, dp[0][1][1] = 1$
•  » » » » » 4 years ago, # ^ |   0 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.
•  » » » » » 4 years ago, # ^ |   0 #include #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<
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 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
•  » » » 11 days ago, # ^ |   0 Yup, thank you
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Took long time to understand. But I got it.
 » 4 years ago, # | ← Rev. 2 →   0 Deleted.