peroooo's blog

Help in combinatorics
By peroooo, history, 4 years ago, In English

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

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

Comments Comments (6)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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 color can 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 color red; and let $$$f(i,j,1)$$$ be the amount of arrangements using the first $$$i$$$ balls and the last $$$j$$$ balls are of color black.

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 sums

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

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

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply