Skip to content
Tutorials Center
My learning

Topics

Lesson 60 of 63 ยท Practice and Review

CSES Advanced and Additional Problems Tour

A tour of harder CSES topics with original Python: meet in the middle, Hamming distance, offline dynamic connectivity, Prufer codes and tree isomorphism, each verified by brute force.

After the core sections of the CSES Problem Set come the Advanced Techniques, Sliding Window Problems and Additional Problems sections. They are less uniform: each problem is a showcase for one specific technique that is rarely needed, but when needed, nothing else will do. This lesson tours five of them: meet in the middle, Hamming distance by bit operations, offline dynamic connectivity, Prufer codes and tree isomorphism.

Everything here is explained in my own words, with original code that has been run against a brute force. The statements are short paraphrases, so read the originals on the CSES site and try them before reading the idea. Several techniques are explained in depth elsewhere in this course, and the links say where.

flowchart TD
    H["Hard problem with tiny n or a hidden structure"] --> A{"n is about 40?"}
    A -- "yes" --> M["Meet in the middle: 2 * 2^20 instead of 2^40"]
    A -- "no" --> B{"Updates removed edges?"}
    B -- "yes" --> D["Segment tree over time + rollback DSU"]
    B -- "no" --> C{"Trees compared or encoded?"}
    C -- "encode" --> P["Prufer code"]
    C -- "compare" --> I["Canonical form (AHU)"]

Each technique is triggered by a recognizable feature of the constraints.

Meet in the middle and Hamming distance

Meet in the Middle. You get n <= 40 numbers and a target x. Count the subsets with sum exactly x. Enumerating 2^40 subsets is impossible, but 2^20 is about a million. Split the numbers into two halves and compute all subset sums of each half. A full subset is a left subset plus a right subset, so for each left sum s you need the number of right subsets with sum x - s: a dictionary lookup. The work is 2^(n/2) per half instead of 2^n.

The same split works whenever a problem has the shape "combine a choice from group A with a choice from group B, and the two parts interact only through one number". Subset sums, "closest sum to a target" (sort one half and binary search), and some graph searches (bidirectional BFS) all fit.

Hamming Distance. You get n binary strings of k bits; find the smallest number of positions in which two different strings differ. Store each string as an integer. The distance between two is the number of one-bits in their XOR, computed with (a ^ b).bit_count(), which is a single machine instruction on modern CPUs. In Python this is fast enough for a few thousand strings, and an early exit when you find distance 1 (the smallest possible) helps a lot on inputs with many strings, since by the pigeonhole principle many strings force close pairs. For the largest inputs, the intended solution uses the same XOR-and-popcount idea in a tight C++ loop.

Python Meet in the middle and minimum Hamming distance

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 test compares meet_in_the_middle with enumeration of every subset on small cases, then runs it on 34 numbers as large as 10^12 (17 billion subsets in total). A second run with the list reversed (a different split) must agree.

Dynamic connectivity: edges come and go

Dynamic Connectivity. A graph starts with no edges. Each event adds an edge or removes an existing one; after each event print the number of connected components. A DSU cannot delete, so the trick is to read all events offline and give every edge a lifetime interval [added, removed). Then:

  1. Build a segment tree over the timeline 0..T-1.
  2. Insert each edge into the O(log T) nodes that cover its interval.
  3. Walk the tree depth first. On entering a node, union its edges in a rollback DSU (union by size, no path compression). At a leaf, read the component count. On leaving, undo the unions made at this node.

Every edge is applied O(log T) times and each application costs O(log n) in the rollback DSU, so the total is O(m log T log n). This is exactly the method explained in Offline Queries, DSU Rollback and Persistence; this time the lifetimes are derived from an event log, which is the form CSES uses. Note the bookkeeping: an edge added at event t and removed at event e exists for states t..e-1, and an edge never removed lives until the end.

Prufer Code. A labelled tree on n vertices corresponds one-to-one with a sequence of n - 2 numbers (see Prufer codes and Cayley's formula). A heap makes encoding O(n log n), but there is a neat O(n) method with a moving pointer: keep a pointer to the smallest leaf; when removing a leaf makes its parent a leaf with a smaller label than the pointer, use it immediately, otherwise advance the pointer to the next leaf. The pointer never moves backwards, which gives linear time. Decoding is the mirror image.

Tree Isomorphism. Are two trees the same shape if you ignore the labels? For rooted trees, use the AHU idea: the canonical form of a vertex is the sorted list of canonical forms of its children; map each distinct list to a small integer. Equal integers at the roots mean isomorphic trees. For unrooted trees, root each tree at its center (one or two vertices found by peeling leaves layer by layer) and compare, trying both centers if there are two.

Python Dynamic connectivity, linear-time Prufer code and tree isomorphism

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 tests are strict: dynamic connectivity is compared with recomputing the graph from scratch after every event, the Prufer code is checked by decoding it back to the original tree, and tree isomorphism is compared with trying every relabeling of the vertices on small random trees.

Other problems in these sections

  • Sliding Window problems (Sliding Window Sum, Minimum, Cost, Median, Mode, Distinct Values): monotonic deques, two heaps with lazy deletion and ordered structures, see Monotonic Stacks, Heaps and Deques.
  • Advanced techniques: Subarray Squares and Houses and Schools (divide-and-conquer DP optimization, see DP Speedups), Genes and Primes, Meet in the Middle (above), Hamming Distance (above), Corner Subgrid Check (bitsets over rows).
  • Additional problems: Inversion Counting, Monotone Subsequences (a construction based on the Erdos-Szekeres theorem), Counting Bits, Maximum Xor Subarray (a binary trie, see Bit Tricks and XOR Problems), Mex Grid Queries, Tree Isomorphism I and II, Visibility Queries, Necessary Cities (block-cut tree), Network Breakdown and Dynamic Connectivity (offline rollback DSU).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does meet in the middle turn 2^40 into about 2^21 operations?

    A subset is a pair (left part, right part). Enumerating each half is 2^20, and matching them is a lookup per left sum.
  2. 2. How is the Hamming distance between two k-bit strings stored as integers computed quickly?

    XOR marks every differing position with a 1, and a population count adds them up in one instruction.
  3. 3. Why must the DSU in offline dynamic connectivity avoid path compression?

    Rollback needs each union to change only two values. Union by size alone keeps find at O(log n).
  4. 4. How are two unrooted trees compared for isomorphism using AHU?

    The center is a property of the shape, so isomorphic trees have matching centers, and canonical forms of rooted trees decide equality.

Summary

  • Meet in the middle splits an exponential search in two halves and joins them with a sort or a hash lookup: 2^(n/2) instead of 2^n.
  • Hamming distance is XOR plus a population count on integers.
  • Offline dynamic connectivity gives each edge a lifetime, hangs it on a segment tree over time and uses a rollback DSU.
  • A Prufer code can be computed in O(n) with a pointer that only moves forward.
  • Tree isomorphism uses canonical ids built from sorted child ids, rooted at the tree's centers.

Next: Training Plans and Virtual Contests