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.

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

1 | tourist | 3619 |

2 | Um_nik | 3493 |

3 | ecnerwala | 3446 |

4 | Radewoosh | 3383 |

5 | ksun48 | 3357 |

6 | yosupo | 3324 |

7 | Benq | 3299 |

8 | maroonrk | 3243 |

9 | apiadu | 3238 |

10 | Petr | 3217 |

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

1 | Errichto | 207 |

2 | Monogon | 197 |

3 | SecondThread | 195 |

4 | vovuh | 189 |

5 | pikmike | 186 |

5 | Um_nik | 186 |

5 | antontrygubO_o | 186 |

8 | Ashishgup | 182 |

9 | pashka | 169 |

10 | Radewoosh | 167 |

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.

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/29/2020 14:11:33 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Now, use stirling's approximation.

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)

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

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.

Maybe up?

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

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

Bump #2.

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

Thanks.