Hello codeforces! I have the next problem and i want to solve it with combinatorics How many ways a+b+c+d=n such that a!=b!=c!=d and 1<=a,b,c,d<n Thanks in advanced. :)

# | User | Rating |
---|---|---|

1 | tourist | 3557 |

2 | Um_nik | 3494 |

3 | Radewoosh | 3344 |

4 | wxhtxdy | 3309 |

5 | LHiC | 3302 |

6 | Benq | 3286 |

7 | mnbvmar | 3274 |

8 | Petr | 3254 |

9 | yutaka1999 | 3190 |

10 | ksun48 | 3170 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 191 |

2 | Radewoosh | 180 |

3 | PikMike | 166 |

4 | antontrygubO_o | 165 |

4 | Vovuh | 165 |

6 | rng_58 | 161 |

7 | majk | 156 |

7 | Um_nik | 156 |

9 | 300iq | 155 |

10 | tourist | 153 |

Hello codeforces! I have the next problem and i want to solve it with combinatorics How many ways a+b+c+d=n such that a!=b!=c!=d and 1<=a,b,c,d<n Thanks in advanced. :)

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/14/2019 20:24:46 (e1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Auto comment: topic has been updated by Ernest0_0Abreu (previous revision, new revision, compare).hint : the answer is 0 or 1 .

i didnt understand that != is unequal, i thought it is factorial and equal ...

Let's solve for 2 numbers: it's $$$N - 1 - ((N + 1) mod 2)$$$, as you choose first number $$$k$$$ and the other one is $$$N - k$$$, but if $$$k = N - k$$$ then such pair is invalid.

For 3 numbers it's you choose first 2 numbers with sum $$$k$$$ (there're $$$k - 1$$$ ways to do that) and the 3rd will be $$$n - k$$$, so it's $$$\sum_{k = 1}^{N - 1} {(k - 1 - ((k + 1) mod 2))} = ((N - 2) \cdot (N - 1)) / 2 - \lfloor{\frac{n}{2}}\rfloor$$$. But this includes, e.g. $$$1, 2, 1$$$. Let's subtract such triplets: their count is $$$2 \cdot \sum_{k = 1}^{\lfloor{\frac{n - 1}{2}}\rfloor} {1} = 2 \cdot \lfloor{\frac{n - 1}{2}}\rfloor$$$. Keep in mind that if N % 3 == 0 the triplet $$$\frac{n}{3}, \frac{n}{3}, \frac{n}{3}$$$ will be counted twice.

Formula for 4 numbers will be a simple exercise hint

Idk why I got downvotes, so implemented it for 3 numbers and 4 numbers

(formula_res functions)

Seems to be correct and $$$O(1)$$$

I'm assuming all four numbers have to be unique (contrary to what you wrote).

Let's assume $$$1 <= a < b < c < d <= n$$$. Changing restriction on numbers to $$$<= n$$$ is inconsequential for solving the original problem. As for fixed ordering, if we solve that problem, we can solve original one by multiply the result by $$$4! = 24$$$ since all the numbers are different.

Let's define $$$a[x][y][z]$$$ as the number of ways we can write $$$y$$$ as a sum of $$$x$$$ distinct numbers, each of which is $$$>= z$$$. We clearly know the answer for $$$x = 1$$$:

Now we can define $$$a[x][y][z]$$$ recursively:

$$$a[x][y][z] = \sum\limits_{i=z}^{y} a[x-1][y-i][i+1]$$$

The answer you need is $$$a[4][n][1] * 24$$$ and this formula allows you to simply compute it recursively with memoization (or dynamic programming) in $$$O(n^3)$$$, but perhaps some optimizations could be made.

There is a pure combinatorics solution if you drop the requirement that number is distinct: $$$\binom{n-1}{3}$$$, but I'm not sure how to nicely encode the distinction requirement – perhaps that recursive formula boils down to something combinatoric.

UPD: Actually, this is probably a huge overkill, since you can trivially get $$$O(n^3)$$$ by brute-forcing smallest three numbers and easily get $$$O(n^2)$$$ by brute-forcing just two smallest numbers. I guess I'll leave it here for fun.

In your do you can either get z or not get one, do it's a sum of 2 other DPS, iiuc