motatoes's blog

By motatoes, history, 7 years ago, In English

Dear CF

I am trying to solve this problem from the gym, I have found that the solution to the problem is the sum of combinations:

nc(N, K) + nc(N, K+1) + nc(N, K+2) + ... + nc(N, N)

where nc(i, j) is the number of combinations i chose j

However the input sizes of N and K are very large and my submission times out. Can you please advise me about a suitable approach to solve this problem?

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

K is quite small, so you can compute that sum by subtracting nc (N, 0) + nc (N, 1) + ... + nc (N, K — 1) from 2 ^ N (which is the sum of all binomial coefficients of order N). With a correct implementation that can work in O(K), but O(NlogMod) is definitely enough to pass as well