overwrite's blog

By overwrite, history, 2 months ago, In English

We are given two pairs (a, b) and (x, y) and we should figure out which is larger C(a, b) or C(x, y) given that all these numbers (a, b, x, y) are at most 10^9.

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

»
2 months ago, # |
Rev. 2   Vote: I like it -11 Vote: I do not like it
$$$ \log \left(\binom{a}{b}\right) = \log \left(\frac{a!}{b! \times (a-b)!}\right) \\ \log \left(\binom{a}{b}\right) = \log(a!) - log(b!) - log(a-b)! \\ $$$

Now, use stirling's approximation.

$$$ n! \approx \sqrt{2 \pi n} \left(\frac{n}{e}\right)^{n} $$$
$$$ ln(n!) \approx n ln(n) - n + \frac{1}{2}ln(2\pi n) $$$

You can add more terms for increased accuracy

https://en.wikipedia.org/wiki/Stirling%27s_approximation

Since log is an increasing function (for base > 1)

$$$ \log \left(\binom{a}{b}\right) < \log \left(\binom{x}{y}\right) \implies \binom{a}{b} < \binom{x}{y} $$$
  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    So, What's the time complexity of this? isn't it linear, like O(max(a,x))?

  • »
    »
    7 weeks ago, # ^ |
    Rev. 3   Vote: I like it +32 Vote: I do not like it

    I don't understand why this got downvoted. This is a perfectly valid approach. The time complexity is O(1). The only problem is this may suffer from precision issues, but I can't see a better solution.

»
7 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Maybe up?

»
7 weeks ago, # |
Rev. 3   Vote: I like it -18 Vote: I do not like it

Let $$$a \leq c$$$ (if not then swap the pairs). Set $$$b = min(b, a-b)$$$ and $$$d = min(d, c-d)$$$. If $$$b \leq d$$$, then $$$\binom{a}{b} \leq \binom{c}{d}$$$ if $$$d-b \leq c-a$$$. I don't know how to handle $$$b > d$$$ though...

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

I would like to see how people would approach this in the contest. Not really CF style problem, but still.

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

Bump #2.

Sorry for bumping the post again, I am interested in a non-approximation solution.

Thanks.