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

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

Can anyone help me with this problem:

Problem: Number of Solution of equation x_1 + x_2 + x_3 + ... x_k = N
for all i: x_i>=0 and x_i<=x_(i+1) constraints:[N<= 10^9 k<=10]

[basically non-decreasing solutions]

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

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

Generate the solution for small N and K and look for a recurrence relation.

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

    Wouldn't you get a O(NK) solution with that?

    By the way, I already thought of an O(NK) solution:

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

      You can get O(logN * K3) by using matrix exponentiation (if your formula allows it).

      EDIT: That formula is not compatible with matrix exponentiation. Maybe there is another one.

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

        I think it is compatible because f(n, k - 1) + f(n - k, k) = f(n - k, k) + f(n - k + 1, k - 1) + ... + f(n - 1, 1).

        For example when k = 3:

        Its time complexity is O(K6logN).

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

The 'x' values must be integers?

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

Hint 1: Prove that the equation is equivalent to y_1 + 2y_2 + ... + ky_k = N. Hint 2: Digit DP. Represent each y_i as a binary number and fix the parity.

→ Ответить