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

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