Advanced Competitive Programming Concepts

These are the articles, dedicated specifically to advanced competitive programming concepts:

  • Modular Multiplicative Inverse and Modular Combinatorics
    In mathematics, particularly in the area of arithmetic, a modular multiplicative inverse of an integer a is an integer x such that the product ax is congruent to 1 with respect to the modulus m.
  • Nth Catalan Number
    Catalan numbers (Cn) are a sequence of natural numbers. Nth Catalan number has applications in many counting problems.
  • How to calculate Binomial Coefficient?
    The recomputations in calculating binomial coefficient (nCr) can be avoided by exploiting optimal substructure and overlapping subproblems.
  • Sieve of Eratosthenes
    The sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking numbers in the range as composite by marking the multiples of each prime as non-prime.
  • Matrix Exponentiation
    Matrix multiplication can be performed in O(logn) by using matrix exponentiation. It is one of the most used techniques.
  • Recursion using Mathematical Induction
    We need to prove the hypothesis that towerOfHanoi (n, A, B, C) will print all the steps to move n disks from A to B using C, with the help of towerOfHanoi (n-1, A, B, C).
  • Brian Kernighan’s Algorithm
    If we subtract a number n by 1 and do it bitwise & with itself (n & (n-1)), we unset the rightmost set bit of number n.
  • Euclidean algorithm for GCD
    Problem Statement – Given two non-negative integers a and b, you’ve to find the Greatest Common Divisor (GCD) of the two numbers. In other words, find the largest number that divides them both in O(log(n)).
  • Bitmasking
    You’ve N elements and you need to find the subsets of these N elements where zero or more of the N elements are included or excluded.

Leave a Reply

Your email address will not be published.