CPPS 101

Competitive Programming and Problem Solving 101

Number Theory

  1. Euclidean Algorithm – Greatest Common Divisor
  2. Lowest Common Multiple of Two Number
    1. UVa 11388 – GCD LCM
  3. Primality Test – Naive Methods
  4. Sieve of Eratosthenes – Generating Primes
    1. Segmented Sieve of Eratosthenes
  5. Prime Number Theorem
  6. Prime Factorization of an Integer
    1. Number of Divisors of an Integer
      1. Highly Composite Numbers
      2. Upper Bound for Number Of Divisors
      3. Divisor Summatory Function
    2. Sum of Divisors of an Integer
  7. Introduction to Modular Arithmetic
    1. UVa 10407 – Simple division
  8. Extended Euclidean Algorithm
    1. Linear Diophantine Equation
  9. Simple Hyperbolic Diophantine Equation
  10. Introduction to Number Systems
    1. Bitwise Operators
    2. Bit Manipulation
  11. Factorial
    1. Number of Digits of Factorial
    2. Prime Factorization of Factorial
    3. Number of Trailing Zeroes of Factorial
    4. Leading Digits of Factorial
  12. Modular Exponentiation
    1. Repeated Squaring Method for Modular Exponentiation
  13. Euler Totient or Phi Function
    1. Euler Phi Extension and Divisor Sum Theorem
      1. SPOJ LCMSUM – LCM Sum
    2. Euler’s Theorem and Fermat’s Little Theorem
  14. Modular Multiplicative Inverse
    1. Modular Inverse from 1 to N
  15. Chinese Remainder Theorem
    1. Chinese Remainder Theorem Part 1 – Coprime Moduli
    2. Chinese Remainder Theorem Part 2 – Non Coprime Moduli

Combinatorics

  1. Stars and Bars Theorem New!!
  2. Prufer Code
    1. Prufer Code: Linear Representation of a Labeled Tree
    2. Application of Prufer Code: Random Tree Generation, Cayley’s Formula and Building Tree from Degree Count

Contest Analysis

  1. Contest Analysis: IUT 6th National ICT Fest 2014, UVa 12830 – 12839
  2. Contest Analysis: BUET Inter-University Programming Contest – 2011, UVa 12424 – 12432