SPOJ Problem GOODB

Good Predictions

Explanation:

This problem requires a simple implementation of nCr, some knowledge of modular multiplicative inverse (you can read here in detail) and some modular multiplication (you can find details here). Solution to the problem is explained below.

We are given, N, W, T and R, where W+T+R=N.

Now, out of N submissions, W submissions are wrong, and thus, no. of ways to choose W submissions out of N submissions will be given by, NCW.
After this, we are left with (N-W) submissions, and no. of ways to choose T submissions out of (N-W) submissions will be given by, (N-W)CT.
And finally, only (N-W-T) submissions are left, and no. of ways to choose R submissions out of (N-W-T) submissions will be given by, (N-W-T)CR.
And finally, we can multiply three results and modulo it with the number 10^9 + 7 and that will be the result.

Pretty easy, huh.

Now, comes the challenge. As we try to find the nCr for large numbers, we find that the result overflows. So, to get the results in the given range, we try to find (nCr) % (10^9 + 7), as explained below.

nCr = n! / (r! * (n-r)!)

                                               n * (n-1) * (n-2) * ... * 3 * 2 * 1
        = -----------------------------------------------------------------------------------------
             (r * (r-1) * (r-2) * ... * 3 * 2 * 1) * ((n-r) * (n-r-1) * (n-r-2) * ... * 3 * 2 * 1)

Now, if we assume, r is minimum of r and (n-r), we can rewrite the formula as,

             n * (n-1) * (n-2) * ... * (n-r+2) * (n-r+1)
        = ------------------------------------------------

                     r * (r-1) * (r-2) * ... * 3 * 2 * 1

We will now find numerator and denominator using modular multiplication w.r.t. (10^9 + 7) and then we need to divide numerator by denominator. Dividing by denominator is equivalent to multiplying numerator with the inverse of denominator w.r.t. (10^9 + 7). So, we find inverse of denominator and multiply it with the numerator.

Now, we have all the three results mentioned above w.r.t. (10^9 + 7). And finally, simple modular multiplication of 3 values will yield the desired result.

Solution:

#include<cstdio>
#include<iostream>
#include<string>
#include<cstdlib>
#include<queue>
#include<stack>
#include<utility>
#include<string>
#include<cstring>
#include<set>
#include<cmath>
#include<vector>
#include<fstream>
#include<map>
#include<list>
#include<algorithm>
#define MOD 1000000007

typedef long long int LLD;
typedef unsigned long long int LLU;

using namespace std;

LLD r[101];

LLD mod_power(LLD a, LLD n, LLD mod){

    // returns (a^n) % mod.
    // '%' represents modulus operation.

    LLD y = 1;
    while(n){
        if(n & 1)
            y = (y * a) % mod;
        a = (a * a) % mod;
        n >>= 1;
    }
    return y;
}

LLD inverse(LLD num){

    // returns the inverse of num w.r.t. (10^9 + 7).
    // uses the property a^(-1) mod p = a^(p-2) mod p.
    return mod_power(num, MOD - 2, MOD);
}

LLD find_ncr_mod(LLD n, LLD r){

    // returns the value of nCr mod (10^9 + 7).

    r = min(r, n-r);
    if(n == 0 || n == 1 || r == 0)
        return 1;

    // find numerator mod (10^9 + 7).
    LLD num = 1;
    for(LLD i = n;i >= n-r+1;i--)
        num = (num * i) % MOD;

    // find denominator mod (10^9 + 7).
    LLD den = 1;
    for(LLD i=2;i<=r;i++)
        den = (den * i) % MOD;

    // find the inverse of obtained denominator w.r.t. (10^9 + 7).
    den = inverse(den);

    // multiply numerator and inverse of denominator and return the result.
    LLD res = (num * den) % MOD;
    return res;
}

int main(){
 
    LLD n, w, t, r, res;
    scanf("%lld%lld%lld%lld", &n, &w, &t, &r);

    // find nCw.
    res = find_ncr_mod(n, w);
    n -= w;

    // find (n-w)Ct and multiply with previous value found.
    res = (find_ncr_mod(n, t) * res) % MOD;
    n -= t;

    // find (n-w-t)Cr and multiply with previous value found.
    res = (find_ncr_mod(n, r) * res) % MOD;
    printf("%lld\n", res);
    return 0;

}

Any suggestions are welcome.

SPOJ Problem BUSYMAN

I AM VERY BUSY

Explanation:

A basic activity selection problem which uses Greedy approach. The implementation mentioned here states to sort the activities in the increasing order of their finishing times. Initially, we choose the first activity. Now, starting from second activity, current activity can be selected if the finish time of previous selected activity is less than or equal to the starting time of current activity.

Solution:

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;

struct act{
    int starting, ending;
}arr[100000];

bool compare(act a, act b){
    if(a.ending < b.ending)
        return true;
    if(a.ending == b.ending)
        return (a.starting < b.starting);
    return false;
}

int main(){
    int t, n, cnt, prevendtime;
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        for(int i=0;i<n;i++)
            scanf("%d%d", &arr[i].starting, &arr[i].ending);
        sort(arr, arr + n, compare);
        cnt = 1;
        prevendtime = arr[0].ending;
        for(int i=1;i<n;i++){
            if(prevendtime <= arr[i].starting){
                cnt++;
                prevendtime = arr[i].ending;
            }
        }
        printf("%d\n", cnt);
    }
}

Any suggestions are welcome.