Skip to content
Tutorials Center
My learning

Topics

Lesson 59 of 63 ยท Practice and Review

CSES Math, String and Geometry Walkthrough

Original walkthrough of CSES math, game, string and geometry problems: divisor sums, derangements, Burnside necklaces, Nim and stair games, borders, minimal rotation, convex hull.

The CSES Mathematics section (about 30 problems), String Algorithms (about 20) and Geometry (about 10) make a good set for a single day of practice: each problem is a classic result that you should be able to write from memory. This lesson explains the idea of the most instructive ones and gives original, tested Python.

The statements are my own paraphrases; solve the originals on the CSES site first and use these notes as hints. Background lessons: Number Theory Toolkit, Counting and Combinatorics, Game Theory, String Algorithms in Contests and Geometry Toolkit.

flowchart LR
    M["Mathematics"] --> M1["Count by divisors: Common Divisors, Sum of Divisors"]
    M --> M2["Count objects: Binomials, Derangements, Necklaces"]
    M --> M3["Games: Nim, Stair Game, Grundy"]
    S["Strings"] --> S1["Prefix function: Borders, Periods"]
    S --> S2["Two-pointer scan: Minimal Rotation"]
    G["Geometry"] --> G1["Cross product: location, intersection, area, hull"]

Three families, each driven by a single reusable primitive.

Mathematics: divisors and counting

Common Divisors. Given up to 2 * 10^5 numbers below 10^6, find the largest d that divides at least two of them. That equals the largest gcd over all pairs. Pairs are too many, but values are small: for each d from the top down, add up how many numbers are multiples of d (using a table of value counts and a stride loop over multiples). The first d with at least two multiples is the answer. The total work is a harmonic sum, max * (1 + 1/2 + 1/3 + ...), about max * ln(max).

Sum of Divisors. Compute the sum of sigma(k) for k = 1..n for n up to 10^12, modulo 10^9 + 7. Count by divisor instead: each d divides floor(n / d) of the numbers, contributing d * floor(n / d). The quotient floor(n / d) takes only about 2 * sqrt(n) different values, and for each quotient q the matching d form a block d..n // q, whose sum is an arithmetic series. So the loop runs O(sqrt n) times.

Binomial Coefficients use a factorial table with modular inverse factorials (see Counting and Combinatorics); the code builds one in two loops and checks it against math.comb.

Christmas Party. Count permutations of n items with no fixed point (derangements). D(n) = (n - 1) * (D(n - 1) + D(n - 2)): the item n swaps into one of n - 1 positions, and either the displaced item also goes to n's place (leaving D(n - 2)) or it does not (leaving D(n - 1)).

Necklace Combinations. Count the ways to color a ring of n beads with m colors, treating rotations as the same. By Burnside's lemma the answer is the average number of colorings fixed by each rotation. Rotating by r positions splits the ring into gcd(n, r) cycles, each a single color, so it fixes m^gcd(n, r) colorings. Grouping the rotations by gcd, the answer is (1/n) * sum over d | n of phi(d) * m^(n/d), which needs the divisors of n and Euler's totient. The code verifies this against a brute force that canonicalizes every coloring.

Python Divisors, derangements, necklaces and binomials

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Games and strings

Nim Game I is the starting point of impartial games: the first player wins exactly when the XOR of the heap sizes is non-zero. Stair Game lets you move any number of coins from stair k to stair k - 1, with stair 0 as the ground. Coins on even stairs are irrelevant (a move by the opponent from an even stair into an odd one can be answered by moving those coins on again), so the game is Nim on the odd-numbered stairs. The code verifies both claims by searching the complete game tree on small positions. For the general theory (Grundy numbers, sums of games) see Game Theory.

Finding Borders. A border of a string is a non-empty proper prefix that is also a suffix. With the prefix function pi (pi[i] is the longest border of the prefix ending at i), the longest border of the whole string is pi[n-1]; the next ones follow the chain k = pi[k - 1]. Finding Periods is the same data: a period p (the string repeats every p letters) exists exactly when n - p is a border length, or p = n.

Minimal Rotation. Among all rotations of a string find the smallest in dictionary order. Brute force costs O(n^2). A linear method keeps two candidate starting points i and j and a match length k: compare s[i+k] with s[j+k] in the doubled string; when they differ, the larger candidate and the k positions after it can all be discarded, because rotations starting inside that stretch are never optimal. This is the same idea as Booth's algorithm and the minimum-expression algorithm.

Python Nim, the stair game, borders, periods and minimal rotation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Geometry: one primitive, many problems

Almost all of the CSES geometry problems can be solved with one function: the cross product cross(o, a, b), twice the signed area of the triangle o, a, b. It is positive for a left turn, negative for a right turn and zero for collinear points. With integer coordinates it is exact: no floating point is needed, and this removes the rounding problems that plague geometry.

  • Point Location Test: the sign of cross(a, b, p) tells whether p is left of, right of or on the line ab.
  • Line Segment Intersection: two segments cross if each one's endpoints lie on opposite sides of the other (strictly different signs of the two cross products). The touching and collinear-overlap cases are handled with an on_segment test.
  • Polygon Area: the shoelace formula sums x_i * y_{i+1} - x_{i+1} * y_i. Keep it doubled to stay in integers.
  • Point in Polygon: shoot a ray to the right and count edge crossings; check for the boundary first.
  • Convex Hull: Andrew's monotone chain sorts the points, then builds a lower and an upper chain, popping while the last turn is not strictly left.

The code checks segments against an exact parametric solution with fractions, the hull against a brute force that identifies corners as points not covered by any triangle or segment of the others, and the polygon area against Pick's theorem (area = inside + boundary / 2 - 1), which gives a completely different way of computing the same number.

Python Cross product, intersection, hull, polygon area and Pick's theorem

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The other problems

  • Mathematics: Exponentiation I and II (use pow(a, b, MOD), and for the second reduce the exponent modulo MOD - 1 by Fermat), Counting Divisors (divisor count with a smallest-prime-factor sieve), Creating Strings II (multinomials), Distributing Apples (stars and bars), Bracket Sequences I and II (Catalan numbers, see Lucas, Catalan and Stirling), Fibonacci Numbers (matrix power or fast doubling), Throwing Dice (matrix power), Prime Multiples (inclusion-exclusion), Grundy's Game (a Grundy table by brute force).
  • Strings: Word Combinations (a trie and a DP over positions), String Matching (prefix function or Z-function), Longest Palindrome (Manacher), Required Substring (automaton DP), Distinct Substrings and Substring Order I/II (suffix array or automaton, see Z, Suffix Array and Aho-Corasick).
  • Geometry: Minimum Euclidean Distance (divide and conquer or a sweep line), Convex Hull (above), Lines and Rectangles intersections (sweep line with a Fenwick tree).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does the Sum of Divisors solution only loop O(sqrt n) times?

    Grouping the divisors d by their quotient q = n // d collapses the sum into about 2 * sqrt(n) blocks.
  2. 2. What does Burnside's lemma compute for the necklace problem?

    Counting orbits of the rotation group equals the average of the fixed-point counts of its elements.
  3. 3. In the Stair Game, why can you ignore the even-numbered stairs?

    Moving coins from an even stair onto an odd stair can be undone by the opponent moving the same coins further down. So only odd stairs decide the game.
  4. 4. What does a positive cross(o, a, b) mean?

    The cross product is twice the signed area of the triangle; positive means counter-clockwise orientation.

Summary

  • Count by divisors with harmonic sums, and group equal quotients to get O(sqrt n) blocks.
  • Derangements use D(n) = (n - 1)(D(n - 1) + D(n - 2)); necklaces use Burnside's lemma with phi and divisors.
  • Nim is the XOR of heaps; the stair game is Nim on odd-numbered stairs.
  • The prefix function yields all borders and periods; a two-candidate scan finds the minimal rotation in O(n).
  • The integer cross product drives point location, segment intersection, area and the convex hull; verify with independent methods such as Pick's theorem.

Next: CSES Advanced and Additional Problems Tour