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.

SPOJ Problem NG0FRCTN

Fractions on Tree

Explanation:

A simple problem which can be solved using recursion.
Our base case will be n = 1, for which numerator will be 1, i.e., (num = 1) and denominator also 1, (den = 1).
For n > 1, we find the value for its parent, say (num / den) by finding the value of n / 2.
Now, 
    if the child is left child, we add numerator to the denominator (den = den + num).
   else, we add denominator to the numerator (num = num + den).
Finally, return the result (num / den).

Solution:

#include<cstdio>
#include<iostream>
#include<vector>

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

using namespace std;

vector<LLD> find_value(LLD n){

    // res[0] denotes numerator and res[1] denotes denominator.
    vector<LLD> res;
    res.resize(2);

    // Base case with n = 1. 
    if(n == 1){
        res[0] = 1;
        res[1] = 1;
        return res;
    }

    // Find the value for parent in res.
    res = find_value(n >> 1);

    // Check for left child.
    if(n == ((n >> 1) << 1))
        res[1] += res[0];
    // Check for right child.
    else
        res[0] += res[1];
    return res;
}

int main(){
 
    LLD n;
    vector<LLD> res;
    res.resize(2);
    while(true){
        scanf("%lld", &n);
        if(!n)
            break;
        res = find_value(n);
        printf("%lld/%lld\n", res[0], res[1]);
    }
    return 0;
}

Any suggestions are welcome.

SPOJ Problem MATHS

Mathematics

Explanation:

The problem demands to find two values.

1. No. of terms in Farey sequence with denominator less than or equal to n.
2. m_th fraction in Farey sequence of n.

For the first value, we use the formula:
Terms in Farey(n) = 1 + φ(1) + φ(2) ... + φ(n-1) + φ(n).
To solve this, we first find out φ values for each n from 1 to 1000000.
We get φ(1) = 1, but to ease further computations, I added 1 to it and then applied dynamic programming to find the corresponding results as described in function "init_and_calculate_phi".

To find the second value, I converted the next term implementation as shown here into C++ which can be found in function "find_term".

Solution:

#include<cstdio>
#include<iostream>

#define size 1000001
typedef long long int LLD;
typedef unsigned long long int LLU;

using namespace std;

LLD phi[size];

void init_and_calculate_phi(){

    // Find the φ value for each n.

    for(int i=1;i<size;i++)
        phi[i] = i-1;
    for(int i=2;i<size/2;i++){
        if(phi[i] == i-1)
            for(int j=i*2;j<size;j+=i)
                phi[j] -= phi[j] / i;
    }

    // Find the no. of terms by adding the sum of previous φ values to current φ value.

    phi[1] = 2;
    for(int i=2;i<size;i++)
    phi[i] += phi[i-1];

    // At the end, phi[n] will store no. of terms
    // in Farey sequence of denominator less than or equal to n.
}

void find_term(int n, int m){

    // If first term is to be found.
    if(m == 1){
        printf("0/1 ");
        return;
    }
    // If second term is to be found.
    if(m == 2){
        printf("1/%d ", n);
        return;
    }
    // If last term is to be found.
    if(phi[n] < 100000 && m == phi[n]){
        printf("1/1 ");
        return;
    }

    // Calculate the value using the next term implementation.
    int a = 0, b = 1, c = 1, d = n, k, tc, td;
    bool flag = false;
    if(m > (phi[n] + 1) >> 1){
        m = phi[n] + 1 - m;
        flag = true;
    }
    for(int i=3;i<=m;i++){
        k = int((n + b)/d);
        tc = c;
        td = d;
        c = k * c - a;
        d = k * d - b;
        a = tc;
        b = td;
    }
    if(flag)
        printf("%d/%d ", d - c, d);
    else
        printf("%d/%d ", c, d);
}

int main(){
 
    int n, m;

    // calculate the no. of terms for 
    // Farey sequence from 1 to (size - 1)
    // and stores in array "phi".

    init_and_calculate_phi();

    while(true){
        scanf("%d%d", &n, &m);
        if(!n && !m)
            break;

        // Find the mth fraction in Farey sequence of n.

        find_term(n, m);
        printf("%lld\n", phi[n]);
    }
 
    return 0;
}

Any suggestions are welcome.