I_love_Captain_America's blog

Combinatorics
By I_love_Captain_America, history, 9 years ago, In English

You have N balls, out of which r1 are of one color, r2 are of another color, r3 are of another color....and so on. There are C colors of balls in total. Balls of same color are identical . You have to choose K balls out of these N balls. What is the best complexity in which this can be done ( not including complexity of precomputation ), and how can we do this?

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

»
9 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

I know two ways of solve this problem.

Suppose that C <= 100, K <= 100 and Ri <= 100. In this case, we can do a simple O(C * K * R) Dynamic Programming approach.

Suppose now that C <= 20, K <= 10^18 and Ri <= 10^18. In this case we can read this problem as count the number of integral solutions to the following equation:

X1 + X2 + X3 + ... + Xc = K, such that 0 <= Xi <= Ri.

So we can solve it using the inclusion-exclusion principle. The complexity is O(C * 2^C). You can read more about it here.

I hope it helps and sorry for my poor english.

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

Although I don't care , but still, why did I get downvoted? Is it a crime to ask about things you don't know?

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

    My guess would be lack of specs (ie. What are the constraints of N, C and K?)
    and perhaps formatting and spelling mistake.

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

      Pun intended?

      Nevertheless, I thought there would be a straight-cut combinatorics formula that runs in O(1) (after some pre-computation that is), which is why constraints didn't seem to matter. But thanks for clarifying.

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

        This is how you find it using direct formula. (Not sure if coding this is easy)

        if N = r1 + r2 + r3 +r4 ... rc

        ans = coefficient of x^k in (1+x+x^2+...x^r1) * (1+x+x^2+...x^r2) * (1+x+x^2+...x^r3) * ... *(1+x+x^2+...x^rc)

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

Do you want to choose K balls out of N randomly, or you want to count the number of ways to do it?

→ Reply
»
7 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Its simple ...you dumb af

→ Reply