# 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

Skip to content
# Category: Competitive Programming

# Shift-AND algorithm for exact pattern matching

# 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

# What is Competitive Programming?

Sticky post
# 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

# Introduction to Prime Numbers

A simple introduction to the Shift-AND algorithm for string matching with example. Continue reading Shift-AND algorithm for exact pattern matching

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

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?

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

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

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