Editorial for ICPC NWERC 2011 A - Binomial Coefficients


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
  • Find n, k such that \binom n k = \frac{n!}{k!(n-k)!} = x
  • Only look for solutions with k \le \frac n 2 and count twice if necessary
  • Approach 1:
    • Loop over k from 0 to \binom{2k}{k} > x
    • Binary search for n
  • Approach 2:
    • For k = 1, solution is \binom x 1
    • For k = 2, solve x = \binom n 2 = \frac{n(n-1)}{2}
    • For k \ge 3, loop over n until \binom n k > x
  • Be really careful with overflows!

Comments

There are no comments at the moment.