Блог пользователя I_love_Captain_America

Combinatorics
Автор I_love_Captain_America, история, 11 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
11 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить
»
11 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
11 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, скрыть # |
 
Проголосовать: нравится -13 Проголосовать: не нравится

Its simple ...you dumb af

→ Ответить