### IHateDynamicProgramming's blog

By IHateDynamicProgramming, history, 5 weeks ago, Hello,

I want to ask for an idea to solve this problem:

Given N <= 10^9 and K <= 5. How many sets (a1, a2, ..., ak) that 1 <= a1 < a2 < a3 < ... < ak <= N and a1 + a2 + ... + ak = N?

For an example, with N = 10, K = 3, the result is 4: (1, 2, 7), (1, 3, 6), (1, 4, 5), (2, 3, 5).

Thanks!  Comments (26)
 » 5 weeks ago, # | ← Rev. 6 →   Nvm, I misread the problem.
•  » » For the above example (N = 10, K = 3). By your idea, the number of sets will be equal with the number of the solutions of X1 + X2 + X3 + X4 = 13 (which is equal 220)?? Am I wrong anywhere? Thanks!
•  » » But every element should be unique in this problem. Stars and bars does not consider this. Can you please explain how will your solution ensure uniqueness?
 » Very similar to an ongoing contest problem.
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   Oops, my bad. I should have checked before commenting. At least I misread the question and failed to solve it correctly lol.
•  » » Can you give me the link to this contest? Please!
•  » » » Yeah sure, after the contest ends, I'll send you the link.
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   Hope it's not a month-long contest — would like to check it out.
 »
•  » » Thank you. I've read it but in my problem, N is so large (about 10^9) so I don't think dynamic programming will be useful. And I think both solutions in your link can't be optimized by matrix mul :((. Are you have any idea?
•  » » »
•  » » » No wonder you diss the dynamic programming approach, hater.
•  » » » » Because I'm bad at dynamic programming lol.
 » I am not sure it is correct approach or not. Here K is very small so we can brute force for each i<=K. A1+A2+A3+..+Ak=N For this equation find the positive integer solution. This solution contains duplicates(Ai=Aj for i!=j) so we have to eliminate that duplicates.
 » 5 weeks ago, # | ← Rev. 2 →   I can suggest the following approach. Let's convert the condition $1 \le a_1 \lt a_2 < a_3 < \dots < a_k \le N$ to more friendly one. For this we introduce new variables $b_i$ with relations $a_1 = 1 + b_1; a_2 = 1 + a_1 + b_2 = 2 + b_1 + b_2; a_3 = 1 + a_2 + b_3 = 3 + b_1 + b_2 + b_3$ and so on. So we can rewrite our original equation $a_1 + a_2 + \dots + a_k = N$ as $kb_1 + (k-1)b_2 + \dots + b_k = N - \frac{k(k+1)}{2}$ with the only conditions $b_i \ge 0$. For example, if $k$ is 4 we have the linear diophantine equation  $4b_1 + 3b_2 + 2b_3 + b_4 = N - 10$where all $b_i$ (I mean $b_i$) are nonnegative. It is also evident that if $N \lt 10$ we have no solutions to the equation.We can find the number of nonnegative solutions of some linear diophantine equation with the help of generating function. For our example generating fuction is  $g(x) = \sum_{k=0} G_k x^k = \frac{1}{(1-x)(1-x^2)(1-x^3)(1-x^4)}$or $(1-x)(1-x^2)(1-x^3)(1-x^4)g(x) = 1$or $(1-x-x^2+2x^5-x^8-x^9+x^{10})g(x) = 1$or $g(x) = xg(x) + x^2g(x) - 2x^5g(x) + x^8g(x) + x^9g(x) - x^{10}g(x)$or $G_n = G_{n-1} + G_{n-2} - 2G_{n-5} + G_{n-8} + G_{n-9} - G_{n-10}$Now you can use matrix exponentiation. Your goal is $G_{N-10}$. I mean $G_{N-10}$. Also you can precalculate all coefficients, initial values and matrices.PS Here are some errors in math processing, sorry.PPS You can find the direct formulae for cases $k = 2,3,4$ on this page.
•  » » Can you explain more about generate function and using it to count non-negative solutions of Diophantine equation? Please!
•  » » » A generating function is a way of encoding an infinite sequence into a function. Let $G(; x)$ be the ordinary generating function (OGF) of the sequence $$. Then, G(x) = \sum_{i=1}^{\infty} a_i x^i. Consider the function g(x)=(1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)(1+x^4+x^8+...). Each term (say x^j) in the expansion of g represents a distinct way of getting the power j on x by choosing 4 terms, one of each bracket series. Much like one of the solutions of b_4 + 2b_3 + 3b_2 + 4b_1 = j. Thus, in the expansion of g, we have exactly one x^j for each way to get sum j. Thus, the coefficient of x^j in the standard form the expansion will be the number of solutions for b_4 + 2b_3 + 3b_2 + 4b_1 = j. Can you see how g is the OGF of our answer sequence? ($$ where $z_{N-10}$ is our answer). The expression can be rewritten as $((1−x)(1−x^2)(1−x^3)(1−x^4))^{-1}$ (The infinite geometric sum property). So we need to find the coefficient of $x^{N-10}$ in this. The above comment by feodorv continues from here. Hope this gave you new insight.Here are some GF blogs, blog_1, blog_2, and the blog that I picked them up from, blog_0.
 » 5 weeks ago, # | ← Rev. 3 →   Misinterpreted the problem, Sorry.
•  » » Downvotes are really an eyeopener
•  » » » Yep. Thought "answer is simply (n-k+1)C(k-1)" doesn't even correspond to test answer.
 » 5 weeks ago, # | ← Rev. 3 →   UPD: Nvm read the problem wrong. Ignore.Use recursion, Let n be the number of identical things to be distributed among r identical boxes with base cases:1) n
 » 4 weeks ago, # | ← Rev. 6 →   Just seen this today, we will use digit DP to solve this. Let $t$ denote the number of digits of $n$ .We have to build $k$ numbers so that:  x_1 x_2 x_3 ... x_t x_1 x_2 x_3 ... x_t + ... x[k]_1 x[k]_2 x[k]_3 ... x[k]_t = n_1 n_2 n_3 n_t WLOG, let's assume that $x_1 < x_2 < ... < x_k$ $f(i, carry, comp, ok)$ is the number of ways to build the answer at $i$ where: $carry$ is the carry number from last column. $k≤5$ so $carry≤4$ $comp$ is a mask. $ith$ bit of $comp$ is $1$ only if there is $j < i$ that $x[i][j] < x[i + 1][j]$ $ok$ is $true$ if $x_1$ already bigger than 0 Pseudo-code f(i, carry, comp, ok){ if(i == t + 1) return ok and !carry; for(nCarry){ for(d1: 0...9) for(d2: 0...9) ... for(dk: 0...9){ if(d1 + d2 + ... + dk + nCarry == n[i] and d1, d2, ..., dk sastify comp & carry){ f(i + 1, nCarry, nComp); } } } } The complexity is $O(t * 4 * 10^k * 2^k)$
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   I have edited a few things, my fault. Here is my implementation of above formula (The code was accepted yay).Bonus: Working with base 2 will considerably reduce time complexity (only $O(32 * 10 * 4^k)$). So $k = 10$ is achievable!And hope you would love DP from now on ^^