IHateDynamicProgramming's blog

By IHateDynamicProgramming, history, 5 weeks ago, In English

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!

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

»
5 weeks ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

Nvm, I misread the problem.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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!

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

»
5 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

Very similar to an ongoing contest problem.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Oops, my bad. I should have checked before commenting. At least I misread the question and failed to solve it correctly lol.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Can you give me the link to this contest? Please!

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Yeah sure, after the contest ends, I'll send you the link.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        Hope it's not a month-long contest — would like to check it out.

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it +46 Vote: I do not like it

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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain more about generate function and using it to count non-negative solutions of Diophantine equation? Please!

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      A generating function is a way of encoding an infinite sequence into a function. Let $$$G(<a_n>; x)$$$ be the ordinary generating function (OGF) of the sequence $$$<a_n>$$$. 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? ($$$<z_n>$$$ 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   Vote: I like it -31 Vote: I do not like it

Misinterpreted the problem, Sorry.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Downvotes are really an eyeopener

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yep. Thought "answer is simply (n-k+1)C(k-1)" doesn't even correspond to test answer.

»
5 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

UPD: Nvm read the problem wrong.

Ignore.
»
5 weeks ago, # |
  Vote: I like it -17 Vote: I do not like it

I like your username. I think in your case hate=love. Right ?

»
4 weeks ago, # |
Rev. 6   Vote: I like it +5 Vote: I do not like it

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]_1   x[1]_2   x[1]_3 ... x[1]_t
        x[2]_1   x[2]_2   x[2]_3 ... x[2]_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   Vote: I like it 0 Vote: I do not like it

    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 ^^