### overwrite's blog

By overwrite, history, 2 months ago,

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.

• +20

 » 2 months ago, # | ← Rev. 2 →   -11 $\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 accuracySince 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 →   0 So, What's the time complexity of this? isn't it linear, like O(max(a,x))?
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   +32 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.
 » 6 weeks ago, # |   +8 Maybe up?
 » 6 weeks ago, # | ← Rev. 3 →   -18 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, # |   0 I would like to see how people would approach this in the contest. Not really CF style problem, but still.
 » 5 weeks ago, # |   0 Bump #2.Sorry for bumping the post again, I am interested in a non-approximation solution.Thanks.