1 of 14

Competitive Programming

Week 10: Math and Geometry

2 of 14

Math and Geometry

Math is one of the best uses of a computer. Computers can do math quickly and precisely, and automate what would take a person hours of work.
Geometry is where computers have trouble, because it usually involves floating point numbers that computers have a hard time representing accurately.

Operators

% is the modulo operator, it returns the remainder of division of two numbers.
+= -= /= *= &= |= are equivalent to a = a + b, a = a - b, etc.
In most programming languages, the division operator / does truncated integer division, so this will be assumed for this class unless stated otherwise.
The ^ operator is usually an exclusive-OR operator, not an exponent.
Python is weird.

Greatest Common Denominator (GCD)

The GCD of two whole numbers is the largest whole number that evenly divides both. For example, gcd(8, 12) = 4.
This is useful for adding fractions and solving spatial problems.
Find the GCD using the Euclidean Algorithm:

gcd(x, 0) = x
gcd(a, b) = gcd(b, a % b) where a > b
Repeat until the base case of gcd(x, 0) is reached, and x is the gcd of a and b.

Example:�gcd(54, 16): 54 % 16 = 6�gcd(16, 6): 16 % 6 = 4�gcd(6, 4): 6 % 4 = 2�gcd(4, 2): 4 % 2 = 0�gcd(2, 0) = 2

Extended Euclidean Algorithm

Find coefficients x and y such that ax + by = gcd(a, b).
Follow a series where x_i = x_{i - 2} - (a / b) * x_{i - 1}, and y_i = y_{i - 2} - (a / b) * y_{i - 1} and�x₀ = 1, x₁ = 0, y₀ = 0, y₁ = 1 while running the Euclidean Algorithm.
End the Euclidean Algorithm when a % b = 0, and return x and y from the previous step.
Example:�gcd(54, 16): 54 % 16 = 6, x = 1 - 3 * 0 = 1, y = 0 - 3 * 1 = -3�gcd(16, 6): 16 % 6 = 4, x = 0 - 2 * 1 = -2, y = 1 - 2 * -3 = 7�gcd(6, 4): 6 % 4 = 2, x = 1 - 1 * -2 = 3. y = -3 - 1 * 7 = -10�gcd(4, 2): 4 % 2 = 0, x = 3, y = -10�gcd(2, 0) = 2 = 54 * 3 + 16 * -10

Least Common Multiple (LCM)

The LCM of two numbers is the lowest positive whole number that is a multiple of both numbers.
lcm(a, b) = (a * b) / gcd(a, b)
LCM can be used to find when two events on different intervals occur at the same time.

Combinations and Permutations

A combination is a grouping of items that does not consider order.�C(n, k) = n! / (k!(n - k)!), where n is the number of items and k is the group size. This returns the number of possible combinations.
A permutation is an ordering of items that considers order.�P(n, k) = n! / (n - k)!, where n is the number of items and k is the group size. This returns the number of possible combinations including all orderings of each combination.
Remember that 0! = 1.
Rubiks cubes have permutations of where the pieces are.

Prime Numbers

If n < 2, n is not prime. 1 is not considered prime.
If n is evenly divisible by any number from 2 to floor(sqrt(n) + 1), n is not prime.

The Sieve of Eratosthenes can be used to quickly determine if a range of numbers are prime.

bool prime[n] = true;�for (int i = 2; i < n; i++) {� if (prime[i]) {� for (int j = i * i; j < n; j += i) {� Prime[j] = false;� }� }�}
Query the resulting array for prime numbers.

Probability and Expectation

The probability of an event can be calculated by dividing the number of outcomes in the event by the number of outcomes in the sample space.
If you roll a die, the probability of rolling an even number is 1 / 2, because there are 3 outcomes that are even numbers out of 6 total outcomes.
The expectation of an event is its probability multiplied by its value.
If you win $10 by rolling a number less than or equal to 3 on the die, your expectation is $5, because the probability is 1 / 2.

Trigonometry

Trigonometry is a branch of math that studies angles, usually relating to triangles.
radians = π / (180 * degrees)

Chinese Remainder Theorem

Determine a number given a set of congruences modulo n_i.
All n_i must be pairwise coprime, meaning the gcd of all n_i is 1.
Recursively solve congruences to find a single congruence that solves the set.
Solve recurrence ax = r mod b by finding c such that ac - by = r.
If ax = r mod b, then x = bn + c
a = 3 mod 5, a = 2 mod 4, a = 2 mod 3�a = 5b + 3, 5b + 3 = 2 mod 4, 5b = 3 mod 4, b = 4c + 3�a = 20c + 18, 20c + 18 = 2 mod 3, 20c = 2 mod 3, c = 3d + 2�a = 60d + 58
Notice that subtracting in modulo always results in a positive value.
2 - 3 mod 4 = -1 mod 4 = 3 mod 4

Geometry

Avoid floating point calculations if you can.
When comparing floating points, use a - b < ε, where ε is a fixed maximum error.
Distance between points is sqrt((x₁ - x₂)^2 + (y₁ - y₂)^2). It is possible for this value to overflow before the computation is complete, so be careful.
Lines can be represented as two points, a point and slope, or slope-intercept.

Intersection of Lines

The intersection of the lines is a point where both lines share the same x and y coordinates.
Simplify line forms into slope-intercept form: y = m₁x + b₁, y = m₂x + b₂.
Let m₁x + b₁ = m₂x + b₂, so x = (b₂ - b₁) / (m₁ - m₂).
Now plug x back into one of the original equations to get y.

Example