CPSIG Week 1: Basic Mathematics.

Learning Material:

Basic Track:

Recursion:
Concept and Implementation:
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=recursionPt1
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=recursionPt2
Uses: Too many to list, Highly useful concept. Basic idea of recursion is a Pre-Requisite before coming to the lecture.

Time Complexity:
Concept:
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=complexity1
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=complexity2

Video Tutorials:
http://www.youtube.com/watch?v=OpebHLAf99Y&list=PL2_aWCzGMAwI9HK8YPVBjElbLbI3ufctn
http://www.youtube.com/watch?v=PFd5s0bHgAQ&list=PL2_aWCzGMAwI9HK8YPVBjElbLbI3ufctn

GCD using Euclid's Algorithm:
Sieve of Erastothenes:
Concept and Implementation: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=math_for_topcoders
Uses: GCD - calculating GCD, LCM. Prime Sieve - Fast calculation of prime numbers in a range.

GCD and Prime Sieve is the minimum you need to learn from this link. Feel free to read the rest too if you have time.

Modular Exponentiation:
Concept: http://en.wikipedia.org/wiki/Modular_exponentiation
Implementation: http://machlearner.blogspot.in/2013/09/modular-exponentiation.html
Uses: Calculating (a^n)%MOD in O(logn) time.

Matrix Exponentiation:
Concept: http://fusharblog.com/solving-linear-recurrence-for-programming-contest/
Implementation: Refer to above link. It is essentially the same as modular exponentiation for numbers, with matrix multiplication instead of normal multiplication. It is highly recommended you implement this on your own and not re-use code.
Uses: Solving Linear Recurrences like Fibonacci numbers in O((d^3)*logn) time where d - dimension of the matrix.

Modular Inverse where MOD is a prime:
Concept: http://en.wikipedia.org/wiki/Modular_multiplicative_inverse
Implementation: http://machlearner.blogspot.in/2013/09/modular-multiplicative-inverse.html
Uses: To calculate nCr%MOD where MOD is prime. nCr = (fact[n]/(fact[r]*fact[n-r]))%MOD = fact[n]%MOD * mod_inv(fact[r]*fact[n-r], MOD)

Advanced Track(for those who have completed all above mentioned concepts):

Primality Testing - Miller Rabbin:
Concept and Implementation: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=primalityTesting
Uses: To check whether a single number is prime or not.

Inclusion-Exclusion Principle:
Concept: http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle
Implementation:
Uses: To calculate probabilities / solve some counting problems where the concept of inclusion-exclusion is involved.

Chinese Remainder Theorem:
Concept: http://en.wikipedia.org/wiki/Chinese_remainder_theorem
Implementation: http://machlearner.blogspot.in/2013/10/chinese-remainder-theorem.html
Uses:  Determine a number n that when divided by some given divisors leaves given remainders

Euler Totient Function:
Concept: http://en.wikipedia.org/wiki/Euler%27s_totient_function
Implementation:
Uses: Too many to list. Please read the wiki page.

Advanced Counting Techniques - Polya Counting, Burnside's Lemma:
Concept:
http://en.wikipedia.org/wiki/Burnside%27s_lemma
http://petr-mitrichev.blogspot.in/2008/11/burnsides-lemma.html
Implementation:
Uses:

Problemset:

Basic Track:
SEQ, SPP, FIBOSUM, FIBTWIST, PRIME1, PRIMEZUK, DCEPCA06, LASTDIG2, GCD2, KOPC12B, RANGZER2, ZSUM

Advanced Track:
PON, PAGAIN, HNUMBERS, POWPOW, NDIVPHI, SQFREE, ETF, PROOT, NGM2

Modular Multiplicative Inverse

Objective: To calculate modular multiplicative inverse of a number.(Refer to the link if you dont know what this term means)

Solution:
Two possible solutions are very nicely explained in the Wikipedia link. So, i will just share C++ implementations using both the methods

Using Extended Euclid:

void extended_gcd(int a, int b, int &gcd, int &x, int &y)
{
    x=0; y=1; gcd=b;
    int u=1,v=0,m,n,q,r;
    while(a!=0)
    {
        q=gcd/a; r=gcd%a;
        m=x-u*q; n=y-v*q;
        gcd=a; a=r; x=u; y=v; u=m; v=n;
    }
}

LL mod_inv(int a)
{
    int gcd,x,y;
    extended_gcd(a,MOD,gcd,x,y);
    if(gcd==1)
        return (LL)((x+MOD)%MOD);
}

Using Euler's Theorem:

Use modular exponentiation from here

Modular inverse is same as mod_exp(a,MOD-2,MOD).

Modular Exponentiation

Objective: To calculate (a^n)%MOD in O(logn) time, where a,n,MOD are constants.

Solution:
a^n = (a^(n/2) )^2 if n is even
           (a^(n-1))*a is n is odd
 Base cases:
a^1 = a
a^0 = 1

So we can solve this problem by recursion.

Code:

int mod_exp(int a, int n, int MOD) {
    if(n == 0)
        return 1%MOD;
    else if(n == 1)
        return a%MOD;
    else if(n&1)
       return (a*mod_exp(a,n-1,MOD))%MOD;
   else
   {
       int ret = mod_exp(a,n/2,MOD);
       return (ret*ret)%MOD;
   }
}

Note: To take care of overflow issues, it is recommended to use long long instead of int.

Iterative Version:

LL modexp(LL a, int n, LL MOD) {
    if(a == 0) {
        if(n == 0) return 1;
        else return 0;
    }
    LL ret = 1;
    while(n > 0) {
        if(n&1) {
            ret *= a;
            if(ret >= MOD) ret %= MOD;
        }
        n >>= 1;
        a *= a;
        if(a >= MOD) a %= MOD;
    }
    return ret;
}

Competitive Programming SIG - Introductory Lecture.

This was an introduction to Competition Programming given by me and Romal in BITS Pilani.

The introductory lecture comprised of an introduction to what is Sport Programming, why to do it, how to get better at it and some motivation to why you should try it. Also, we talked about how we are going to handle the Competitive Programming Special Interest Group (CPSIG) lectures over the course of this semester.

Visit the page www.facebook.com/CPSIG for regular updates on this Interest Group.

For those you missed it here are the lecture slides and the motivational video:

Slide

Video:

For more motivation and a story about Gennady Korotkevich (the child prodigy mentioned in the lecture) visit Competition Programming Resources -> Motivational and Advice on this blog.