TLE in BINXOR

help
1

I used the same approach as in the video editorial and I’m getting TLE for sub task 3… I don’t understand which part of my code needs to be optimized…

Here’s my solution:
https://www.codechef.com/viewsolution/28577507

Here’s the link to the question:

1 Like
2

You need a faster way to find the value of NCr.

Your method of finding NCr leads to a time complexity of O(N^2), which results in TLE for the final subtask, as N can be as big as 2*10^5.

A faster way to compute NCr is as follows:

  1. Notice that NCr = \frac{N!}{r!*(N-r)!}. So,
  2. Precompute all factorials upto N.
  3. Now, we just need to learn how to do the modulo under division sign. This can be achieved if we find the modular multiplicative inverse of r!*(N-r)! with respect to 10^9+7. This can be found in log(10^9+7) time every time.
  4. Thus, to get a particular NCr, we can get the factorials in constant time from the precomputed factorial array, and then multiply N! with the modular multiplicative inverse of the denominator.

You can refer to my submission here: CodeChef: Practical coding for everyone

Hope it helped :slight_smile:

4 Likes