Ernest0_0Abreu's blog

By Ernest0_0Abreu, history, 7 days ago, In English,

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

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

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 days ago, # |
  Vote: I like it -33 Vote: I do not like it

hint : the answer is 0 or 1 .

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

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

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

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

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

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

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