PoIycarp's blog

How to calculate solutions to x+y+z = u+v+w, 0 <= x, y, z, u, v, w < n.
By PoIycarp, history, 8 months ago, In English

So I'm trying to solve this problem but my solution has O(n^6) complexity and I don't know how you can do this faster.

int ans = 0;
for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
        for(int k = 0; k < n; k++){
            for(int x = 0; x < n; x++){
                for(int y = 0; y < n; y++){
                     for(int z = 0; z < n; z++){
                         if(i + j + k == x + y + z) ans++;
                     }
                 }
            }
        }
    }
}
cout << ans << "\n";

I looked up the sequence on OEIS but there isn't any other relevant information.
https://oeis.org/search?q=1+%2C+20+%2C+141+%2C+580+%2C+1751&language=english&go=Search
I need to calculate this fast for n <= 100000.

  • Vote: I like it
  • -12
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by PoIycarp (previous revision, new revision, compare).

→ Reply
»
8 months ago, # |
← Rev. 4   Vote: I like it +9 Vote: I do not like it

you can calculate number of tuples $$$0 \leq a, b, c \leq x$$$ where $$$a + b + c = x$$$ in $$$O(1)$$$, call this $$$w$$$, you can sum $$$w^2$$$ for all $$$1 \leq x \leq 3 \cdot n$$$

number of tuples can be calculated by $$$\binom{x + 2}{2}$$$ i think.

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    This is not true because in your solution, one of a, b, c may become greater than n-1 But this problem is solved with pie ( which one is greater than n-1) in O(1) Sorry if my English is not good

    → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    with inclusion-exclusion:

    int ans = 0;
for(int i = 0; i <= (n-1)*3; i++){
	
	int tot = choose(i+2, 2);
	
	if(i >= n){
		int c = mul(3, choose((i-1*n)+2, 2));
		tot = add(tot, mul(-1, c));
	}
	
	if(i >= 2*n){
		int c = mul(3, choose((i-2*n)+2, 2));
		tot = add(tot, mul(+1, c));
	}
	
	ans = add(ans, mul(tot, tot));
}
    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      in short, ans[sum] =

      (+) (number of ways to choose 3 elements that sum up to "sum")

      (-) (number of ways to choose 3 elements that sum up to "sum" but one of them is greater or equal to n) * (number of ways to choose that one element from the 3 chosen elements)

      (+) (number of ways to choose 3 elements that sum up to "sum" but two of them are greater or equal to n) * (number of ways to choose those two elements from the 3 chosen elements)

      → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

correct me if i am wrong,

iterate on the sum (say $$$s$$$), we can as it'll be $$$\leq 3 n$$$

now we can calculate the number of solutions to $$$x + y + z = s$$$ using stars and bars, let that be equal to $$$c$$$

finally you choose two set of solutions and equate them so your answer will be $$$c * c$$$

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    bro the main part is finding c(which is doable using a diophantine equation) but you gonna calculate that for every answer from 0 to n-1 since you can't sum them up and raise it to the power of 2, why? because:
    $$$(x + y)^2 \neq x^2 + y^2$$$ there is $$$2xy$$$ remaining which requires everything separately

    even if we could do that, finding c is a bit annoying using c++ since it can't do easy combinatorics

    → Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

There is a formula on Oeis:

$$$f(n) = \frac{n(11n^4+5n^2+4)}{20}$$$

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can u link the page?

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      It's just the link in his blog:

      link

      Just read all lines. You will see the formula

      → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah thats why I linked it , but how can you write an actual algorithm to solve this? This task was given at the national olympiad in my country and a lot of people solved it, but somehow I can't think how you can solve this any other way, of course they didn't have access to OEIS.

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      You can just believe that the answer is polinomial, and interpolate it:)

      → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ummm? they use paper and induction or recursive functions in combinatorics to get to a formula?

      there is also this recursive function formula:
      $$$f_n = 6f_{n-1} - 15f_{n-2} + 20f_{n-3} - 15f_{n-4} + 6f_{n-5} - f_{n-6}$$$
      If anyone found out what it represents and the logic behind it please reply

      → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Let $$$f = (1 + x + ... + x^{n - 1})$$$

      If you find $$$f^3$$$ you will solve the problem because $$$f [ x^k ]$$$ = number of solutions $$$x + y + z = k$$$

      So you need only multiply polinomials. You can do it in $$$O(n^2)$$$ naive, or using fft

      → Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Here's an elementary solution that doesn't use any generating functions or mystic formulas. Probably, this is what people in your national OI used.

Let $$$\mathrm{dp}[k][s]$$$ be the number of $$$k$$$-tuples of integers in $$$0 \ldots n - 1$$$ summing to $$$s$$$. That is:

  • $$$\mathrm{dp}[2][s]$$$ is the number of pairs $$$(x, y)$$$ such that $$$0 \le x, y < n$$$ and $$$x + y = s$$$.
  • $$$\mathrm{dp}[3][s]$$$ is the number of triples $$$(x, y, z)$$$ such that $$$0 \le x, y, z < n$$$ and $$$x + y + z = s$$$.

It should be clear that

$$$ \mathrm{dp}[k][s] = \mathrm{dp}[k - 1][s - n + 1] + \mathrm{dp}[k - 1][s - n + 2] + \cdots + \mathrm{dp}[k - 1][s]. $$$

If $$$s - n + 1$$$ is negative, start summing from 0 instead. How to calculate this quickly? Use prefix sums:

for (int k = 1; k <= 3; k++) {
    sdp[k - 1][0] = dp[k - 1][0];
    for (int i = 1; i <= 3 * n; i++)
        sdp[k - 1][i] = sdp[k - 1][i - 1] + dp[k - 1][i];

    for (int s = 0; s <= 3 * n; s++) {
        dp[k][s] = sdp[k - 1][s];
        if (s - n >= 0)
            dp[k][s] -= sdp[k - 1][s - n];
    }
}

Now the answer is $$$\sum_{s = 0}^{3n - 3} \mathrm{dp}[3][s]^2$$$.

→ Reply