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 re-computations 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.
  • Implementing Mathematical Exponential (O(logn))
    Calculating An mod p, where A can be as large as 1018 and p is a prime (109 + 7) using inbuilt method pow(), will result in integer overflow. Also, calculating exponential, iteratively will result in TLE (Time Limit Exceeded) when along with A, n is also as large as 1012.
  • Matrix Exponentiation
    Nth Fibonacci number can be found in O(logn) by using matrix exponentiation. It is one of the most used techniques in competitive programming.
  • 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.
  • Special Data Structures
    Segment Tree, Trie, Priority Queue, and Heap are some of the data structures that are most frequently used in competitive programming.

If you are new to programming or preparing for a software engineering interview, the following guide provides a roadmap for your preparation: How to prepare for coding interview of Google, Microsoft, Amazon & Facebook?

Leave a Reply

Your email address will not be published. Required fields are marked *