Shift-AND algorithm for exact pattern matching
A simple introduction to the Shift-AND algorithm for string matching with example. Continue reading Shift-AND algorithm for exact pattern matching
Category: Competitive Programming
Johnson Rule
Matrix Computation
Centroid Decomposition
SQRT Decomposition on Tree
Segment Tree
Heavy-Light Decomposition
Binary Indexed Tree 2D (BIT-2D)
Binary Indexed Tree (BIT)
Min Cost Max Flow
Maximum Matching on Bipartite Graph – Hungarian Algorithm
Dinic Algorithm (2)
Dinic Algorithm (1)
Dijkstra Algorithm
Bellman-Ford Algorithm
Warshall-Floyd Algorithm
Bridges
Articulation Points
Two-Sat (2-SAT)
Strongly Connected Component – Tarjan Algorithm
Disjoint Set Union
Convex Hull Trick
Convex Hull
Pick Theorem
Sweep Line Algorithm for Closest Pair problem
Orthogonality of 2 lines
Collinearity of 3 points
Equation of a circle given center and radius
Equation of line passing through 2 points
Rotate a point around another point
Area of a triangle
The angle between 2 vectors
Center and Radius of a circle given 3 points
Aho Corasick
Suffix Array
KMP Algorithm
Z-algorithm
Ternary Search
Binary Search
Introduction to Hashing
Hashing is a technique in Competitive Programming which is mostly used with string. In many cases, using hash can relieve you from doing other complex data structures or complicated dynamic programming optimization. A drawback of hashing is that: you are not completely sure that your solution will work on all cases. If you are really really unlucky, your solution may fail one test-case and receive Wrong Answer. But the chance of failing is very low, and you can even lower that chance by using multiple hashes. So, in the scope of a programming contest, hashing is acceptable and can give … Continue reading Introduction to Hashing
What is Competitive Programming?
Definition Competitive Programming is a sport, which requires participants to program to solve computational problems. The score a participant gets is normally calculated based on how many problems he solved, the difficulty of the problems, the time he spends on each problem and the number of attempts he made before successfully solve each problem. Each problem is well-defined, clear and has concrete limits and constraints. A competition can be held locally or globally. There are some annual global competitions, like IOI (International Olympiad in Informatics) – an individual-based contest for high-school students, ICPC (International Collegiate Programming Contest) – a team-based contest … Continue reading What is Competitive Programming?
Sticky post
Competitive Programming
Getting Started What is Competitive Programming? A summary of modern C++ features Number Introduction to Prime Numbers Sieve of Eratosthenes Rabin-Miller’s Test for Primality GCD, LCM and Euclidean Algorithm Extended Chinese Remainder Theorem Euler’s totient function Basics of Factorization And Combinatorics Search Binary Search Ternary Search String Z-algorithm KMP Algorithm Suffix Array Aho Corasick Geometry Center and Radius of a circle given 3 points The angle between 2 vectors Area of a triangle Rotate a point around another point Equation of line passing through 2 points Equation of a circle given center and radius Collinearity of 3 points Orthogonality of … Continue reading Competitive Programming
Basics of Factorization And Combinatorics
Euler’s totient function
Rabin-Miller’s Test for Primality
Chinese Remainder Theorem
GCD, LCM and Euclidean Algorithm Extended
Sieve of Eratosthenes
Sieve of Eratosthenes is a wonderful technique to get a list of prime numbers in the range (1, n]. It also supports testing for primality of any number in O(1) after pre-processing. The pre-processing phase has time complexity in original version and in enhanced version. Original Sieve of Eratosthenes This technique relies on one simple observation: if x is a composite number (or we can say: if x is not a prime number), then there exists a prime number p which is a divisor of x, and of course, p < x. So, if for every prime number p such … Continue reading Sieve of Eratosthenes
Introduction to Prime Numbers
I. What is a Prime Number? A number is called prime if it satisfies all the following conditions: is a natural number, greater than 1, has only 2 divisors: 1 and itself. For example, are the first prime numbers. If so, what is NOT a prime number? not a natural number (e.g. a fraction, like or ), less than or equal to 1 (e.g. -3, 0, 1 are NOT prime), can be formed by multiplying 2 natural numbers less than itself (e.g. is NOT a prime number). II. Why is Prime Number important? In the modern world, prime numbers are … Continue reading Introduction to Prime Numbers