I_love_Captain_America's blog

Combinatorics
By I_love_Captain_America, history, 11 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

»
11 years ago, hide # |
← 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
»
11 years ago, hide # |
 
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
»
11 years ago, hide # |
 
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
»
9 years ago, hide # |
 
Vote: I like it -13 Vote: I do not like it

Its simple ...you dumb af

→ Reply