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

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

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
  • Проголосовать: не нравится

»
9 лет назад, # |
← 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.

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 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?

→ Ответить
  • »
    »
    9 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

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

      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.

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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)

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

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

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

Its simple ...you dumb af

→ Ответить