Confused101's blog

combinatorics problem
By Confused101, history, 9 years ago, In English

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]

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

»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

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

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

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

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

      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.

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

        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).

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

The 'x' values must be integers?

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

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.

→ Reply