Good Predictions | Editorial by Muhammad

/** In the name of ALLAH **/

written by : Muhammad Shahriar Alam.

GOODB - Good Predictions
This problem can be solve using [binomial coefficient. ](https://cp-algorithms.com/combinatorics/binomial-coefficients.html)

We know that we can take k elements from n elements in nCk ways.

Here,

nCr = n! / ( k!  (n-k)!).

Okay. Now what is our question. We have N verdicts. Where there will be W wrong answers(WA), T time limit exceeded (TLE) , R run time errors (RTE).

Now we can take W wrong answer  from N verdict in NCW ways. Now we have taken W wrong anwer verdict from N verdicts. Now we have N-W remaining verdicts.

Now we can take T Time limit exceeded from N-W verdicts in     N-WCT ways. Now we have taken T verdicts from N-W verdicts.

Now we have N-W-T remaining verdicts.

Now we can take R Run time errors from N-W-T verdicts in N-W-TCR ways. Now we have taken T wrong anwer verdict from N-W-T verdicts.

So our answer is:

ans = NCW * N-WCT * N-W-TCR.

Here *(astaric) = multiplication.

Complexity :

Complexity depends on how you are calculating nCk .

O(n) solution :

We can use  nCr = n! / ( k!  (n-k)!)  this formula for O(n) solution.

First we will calculate all factorials of 1 - 300 and then will calculate nCr in O(1).  We will need modular [Modular Multiplicative Inverse](https://cp-algorithms.com/algebra/module-inverse.html) here. Don't worry. You need not to understand this. You can just use the code here. Read the comments of my code carefully. In Sha ALLAH this will be enough.

[My Code](https://paste.ubuntu.com/p/ysCr76wxmF/)

O(n2) solution :

We will calculate all nCr using dynamic programming and than calculate our solution.

[My Code](https://paste.ubuntu.com/p/jKVQdF2XxR/)

Good Predictions | Editorial by Muhammad

Download submission

All caught up!

View submission

Is your resume even shortlisted?