There are N RED balls and M BLACK balls output should be the total number to arrangements with atmost K balls can be together.

ex: Input: n = 3 m = 2 k =1 Output: 1 explantion: RBRBR

input: n = 2 n = 2 k =1 output: 2 explantion: RBRB BRBR

# | User | Rating |
---|---|---|

1 | tourist | 3619 |

2 | Um_nik | 3493 |

3 | ecnerwala | 3446 |

4 | Radewoosh | 3383 |

5 | ksun48 | 3357 |

6 | yosupo | 3324 |

7 | Benq | 3299 |

8 | maroonrk | 3243 |

9 | apiadu | 3238 |

10 | Petr | 3217 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 207 |

2 | Monogon | 196 |

3 | SecondThread | 195 |

4 | vovuh | 188 |

5 | pikmike | 186 |

6 | Um_nik | 185 |

6 | antontrygubO_o | 185 |

8 | Ashishgup | 182 |

9 | pashka | 169 |

10 | Radewoosh | 167 |

There are N RED balls and M BLACK balls output should be the total number to arrangements with atmost K balls can be together.

ex: Input: n = 3 m = 2 k =1 Output: 1 explantion: RBRBR

input: n = 2 n = 2 k =1 output: 2 explantion: RBRB BRBR

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/31/2020 06:37:16 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Well, I will suppose that the correct statement of the problem is:

Given $$$n,m,k$$$, you have to print the amount of ways of arranging all the $$$n+m$$$ balls, such that at most $$$k$$$ balls of

same colorcan be adjacent.Let’s use

Dynamic Programming. Let $$$f(i,j,0)$$$ be the amount of arrangements using the first $$$i$$$ balls and the last $$$j$$$ balls are of colorred; and let $$$f(i,j,1)$$$ be the amount of arrangements using the first $$$i$$$ balls and the last $$$j$$$ balls are of colorblack.Transition are very straightforward. And you can obtain a solution with $$$O((n+m)\cdot k^2)$$$ time complexity. The time complexity can be reduced to $$$O((n+m)\cdot k)$$$ by using

prefix sumscan you send the DP solution I just started learning dynamic programming ? that will be very helpful I am very frustrated with this problem

is there any generalized equation to solve or I have to iterate over every combination

This does not solve the problem because it ignores the numbers of balls of each individual color used. Thus for the first example input, your idea will produce an output of 2, counting strings "RBRBR" and "BRBRB", even though only one of these is valid. This is, of course, easy to account for by expanding the DP state space so that $$$f(i, j, 0, c)$$$ is the number of arrangements using $$$i$$$ red balls and $$$j$$$ black balls with the last same-colored block containing exactly $$$c$$$ red balls, and likewise $$$f(i, j, 1, c)$$$ for arrangements with the last same-colored block containing $$$c$$$ black balls.

However, the time complexity will suffer: This approach needs $$$O(nmk)$$$ operations when implemented naively. It can be optimized to $$$O(nm)$$$ by using queues to perform transitions efficiently, or to $$$O((kn)^3 \log(m))$$$ by using matrix multiplication to perform long-range generalized transitions. The latter approach can be optimized to $$$O(k^3 n^2 \log(m))$$$ by noticing that the transition matrices are convolution-like (nearly block-circulant) and implementing those naively, or to $$$O(k^3 \min(n, m) \log(n) \log(m))$$$ by implementing them with FFT.

You can also try this question after you are over with this https://codeforces.com/problemset/problem/118/D In this question there are two parameters K1 and K2 instead of one single K

thanks man