Ernest0_0Abreu's blog

By Ernest0_0Abreu, history, 7 days ago, ,

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

• -15

 » 5 days ago, # |   0 Auto comment: topic has been updated by Ernest0_0Abreu (previous revision, new revision, compare).
 » 5 days ago, # |   -33 hint : the answer is 0 or 1 .
•  » » 5 days ago, # ^ |   +40 i didnt understand that != is unequal, i thought it is factorial and equal ...
 » 5 days ago, # | ← Rev. 4 →   +8 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
•  » » 4 days ago, # ^ |   +8 Idk why I got downvotes, so implemented it for 3 numbers and 4 numbers(formula_res functions)Seems to be correct and $O(1)$
 » 5 days ago, # | ← Rev. 3 →   0 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$: $a[1][y][z] = 1$, for any $y$, where $z <= y$ $a[1][y][z] = 0$, for any $y$, where $z > y$ 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.
•  » » 5 days ago, # ^ |   0 In your do you can either get z or not get one, do it's a sum of 2 other DPS, iiuc