Test shapes

Uniform random is almost never the interesting case. A solution that is wrong is usuallywrong on a shape — a long chain, a star, a plateau of equal values, all points collinear —and uniform sampling produces those with probability ~0. The job is to enumerate the shapesthe problem admits and build each one deliberately.

With eolymp.h, most shapes are one call

A new generator is written with eolymp.h (Write a test generator),and its second header, eolymp-shapes.h, builds most of the shapes on this page — includingthe relabelling that §1 insists on:

#include <eolymp.h>
#include <eolymp-shapes.h>

int main(int argc, char** argv) {
    eo::generator g(argc, argv);
    int n = g.option<int>("n", 2, 200000);
    std::string kind = g.option<std::string>("shape", {"random", "uniform", "path", "star", "caterpillar", "broom", "binary", "dumbbell"}, "random");

    eo::graph tree = eo::shapes::tree(g.rng("tree"), n, kind);
    std::vector<long long> w = g.rng("weights").ints(n - 1, 1, 1000000000);
    std::vector<eo::edge> edges = eo::shapes::presented(g.rng("labels"), tree);

    g.out.line(n);
    for (int at = 0; at + 1 < n; at++) g.out.line(edges[at].u, edges[at].v, w[at]);
}

Every call is in eo::shapes:: and takes a stream (g.rng("label")) where it draws:

Two differences from the recipes below: convex_position puts every point on the hull'sboundary but not strictly convex — many triples come out collinear — so it is not the generatorfor "no three points are collinear"; and a shape the library lacks is built by hand fromg.rng(...), never from testlib's rnd.

The code blocks below are written with testlib's rnd. They explain what each shape is andwhy it breaks solutions, and they are what a testlib generator uses(Write a test generator with testlib.h).

1. The rule that applies to every graph and tree

Relabel the vertices and shuffle the edge list before printing. Always.

void emit(vector<pair<int,int>> e, int n) {
    vector<int> lab = rnd.perm(n, 1);                  // 1..n permuted
    for (auto &p : e) { p.first = lab[p.first-1]; p.second = lab[p.second-1]; }
    for (auto &p : e) if (rnd.next(0, 1)) swap(p.first, p.second);   // endpoint order
    shuffle(e.begin(), e.end());                       // testlib's shuffle
    for (auto &p : e) println(p.first, p.second);
}

Skip this and every tree you emit is rooted at 1 with parent < child and edges in BFSorder. A wrong solution that happens to process vertices in input order will pass, and anO(n²) solution may never hit its worst case. This is the most common defect in treegenerators — it is invisible in review because the tree is random; only its presentationis not.

2. Trees

2.1 The three-line "random tree" — know what it actually is

for (int v = 2; v <= n; v++)
    e.push_back({rnd.next(1, v - 1), v});

This is a random recursive tree, not a uniform random tree. Its depth is Θ(log n):

So it is a bushy tree. It will never stress a recursive DFS, never produce a long path,and never trigger stack overflow. Perfectly good as a default case — but it is one shape,not "a random tree".

2.2 Controlling depth with wnext

rnd.wnext(a, b, w) returns the max of w+1 samples when w > 0 (bias high), the min of|w|+1 samples when w < 0 (bias low). Biasing the parent toward v-1 deepens the tree:

int p = rnd.wnext(1, v - 1, w);     // larger w  ⇒  deeper

Measured at n = 100,000:

wnext cannot give you a bamboo. Even w = 50 reaches depth 429 out of 100,000 — still0.4% of n. If you need Θ(n) depth, construct it explicitly (§2.4). This is worth statingbecause "use wnext for a deep tree" is a common and insufficient answer.

2.3 Uniform over labelled trees — Prüfer

The only way to sample uniformly from all n^(n-2) labelled trees:

vector<pair<int,int>> randomTree(int n) {
    if (n == 1) return {};
    if (n == 2) return {{1, 2}};
    vector<int> code(n - 2);
    for (int &x : code) x = rnd.next(1, n);

    vector<int> deg(n + 1, 1);
    for (int x : code) deg[x]++;

    vector<pair<int,int>> e;
    int ptr = 1; while (deg[ptr] != 1) ptr++;
    int leaf = ptr;
    for (int x : code) {
        e.push_back({leaf, x});
        if (--deg[x] == 1 && x < ptr) leaf = x;
        else { ptr++; while (deg[ptr] != 1) ptr++; leaf = ptr; }
    }
    e.push_back({leaf, n});
    return e;                       // O(n)
}

A uniform labelled tree has max degree Θ(log n / log log n) and diameter Θ(√n) — between therecursive tree and a path. Use it when the statement says "a tree is given" with no furtherstructure and you want the honest average case.

2.4 Explicit shapes — the ones that actually break solutions

// bamboo / path: depth n, kills recursive DFS, worst case for LCA-by-climbing
for (int v = 2; v <= n; v++) e.push_back({v - 1, v});

// star: one vertex of degree n-1, kills adjacency-list scans and per-vertex loops
for (int v = 2; v <= n; v++) e.push_back({1, v});

// caterpillar: a spine with legs — long path AND high degree at once
int spine = n / 2;
for (int v = 2; v <= spine; v++) e.push_back({v - 1, v});
for (int v = spine + 1; v <= n; v++) e.push_back({rnd.next(1, spine), v});

// broom: path of length n/2, then a star at the end
for (int v = 2; v <= n / 2; v++) e.push_back({v - 1, v});
for (int v = n / 2 + 1; v <= n; v++) e.push_back({n / 2, v});

// complete binary tree: perfectly balanced, depth log n, no skew to exploit
for (int v = 2; v <= n; v++) e.push_back({v / 2, v});

// k-ary
for (int v = 2; v <= n; v++) e.push_back({(v - 2) / k + 1, v});

// dumbbell / double star: two hubs joined by a path — worst case for centroid logic
// spider: k legs of equal length from one centre — worst case for "k-th ancestor"

Two-hub dumbbell deserves special mention: many centroid-decomposition and"find the middle" solutions have an off-by-one that only shows up when the tree has exactlytwo centroids, which requires an even-length path between equal halves.

2.5 Rooted trees, and the parent-array format

If the output format is a parent array rather than an edge list, you cannot shuffle edges —but you must still relabel, subject to the format's constraint. If the format demandsparent[v] < v, then relabelling must preserve a topological order: generate the shape,compute any valid topological numbering, and permute within that constraint (e.g. shufflesiblings). Otherwise the parent array leaks the construction order.

2.6 Weights

Do not always use rnd.next(1, W). Weight distribution matters as much as topology:

• all weights equal (BFS becomes valid; catches solutions that assume distinct)

• all weights 1 except one huge (tests overflow and tie-breaking)

• weights near the maximum so path sums overflow int (catches missing long long)

• weights 0 where the statement permits (catches dist == 0 sentinels)

• negative weights where permitted (catches Dijkstra used instead of Bellman–Ford)

3. Graphs

3.1 Connected, simple, exactly m edges

set<pair<int,int>> seen;
vector<pair<int,int>> e;
auto add = [&](int a, int b) {
    if (a == b) return false;
    auto key = minmax(a, b);
    if (!seen.insert({key.first, key.second}).second) return false;
    e.push_back({a, b});
    return true;
};
for (int v = 2; v <= n; v++) add(rnd.next(1, v - 1), v);   // spanning tree first
while ((int)e.size() < m) add(rnd.next(1, n), rnd.next(1, n));

Verified at n=2000, m=5000: 5000 edges, all unique, no self-loops.

The rejection loop is only safe while the graph is sparse. As m approachesn(n-1)/2, rejection sampling stalls — every candidate collides. Switch strategies atroughly m > n(n-1)/4: enumerate all pairs, shuffle, take the first m. For large densegraphs, generate the complement instead and invert.

Always ensuref((int)e.size() == m, "...") after the loop, and cap the attempt count so agenerator that cannot reach m fails loudly instead of hanging a package build.

3.2 The shapes

// complete graph  — m = n(n-1)/2, the density ceiling
// cycle           — every vertex degree 2, the sparsest 2-connected graph
// cycle + chords  — near-tree with just enough cycles to break tree algorithms
// grid r×c        — planar, predictable diameter √n, worst case for BFS-flood
// bipartite       — pick sides, only cross edges; kills odd-cycle assumptions
// complete bipartite K_{a,b} with a small — dense but low-diameter
// clique + isolated vertices — max edges with min vertices touched
// many components — c disjoint pieces; catches "assume connected" solutions
// star of cliques — cliques joined at one cut vertex; worst case for articulation points

3.3 DAGs

vector<int> ord = rnd.perm(n, 1);             // random topological order
// then every edge goes ord[i] -> ord[j] with i < j
for (...) { int i = rnd.next(0, n-2), j = rnd.next(i+1, n-1); add(ord[i], ord[j]); }

Never emit vertices in topological order — that is the same leak as §1, and it makes asolution that ignores the actual topological sort pass anyway.

Special DAGs: a single long chain (longest-path worst case), a "layered" DAG with √nlayers of √n nodes (maximal path count), and a DAG with one source and one sink andexponentially many paths (catches path-counting overflow).

3.4 Functional graphs

f(i) for each i — every vertex out-degree exactly 1. Shapes: one big cycle (period n),many small cycles, a long "rho" (tail into a small cycle — worst case for cycle detection),all self-loops. Cheap to generate, and a distinct family from general digraphs.

3.5 Multigraphs and self-loops

If the statement permits them, generate them — solutions routinely forget. If it forbidsthem, ensuref that none were produced. Never leave it ambiguous: this is the most commonmismatch between a generator and its validator.

4. Arrays and sequences

// uniform
for (int &x : a) x = rnd.next(1, V);

// all equal / few distinct  — kills "assume distinct", exercises ties everywhere
int k = rnd.next(1, 3);
for (int &x : a) x = rnd.next(1, k);

// sorted / reverse sorted / nearly sorted (sorted with s random swaps)
// plateau: long runs of equal values
// two values only: the classic worst case for partition-based algorithms
// alternating high/low: worst case for "merge adjacent" heuristics
// all maximum: overflow bait — sum = n * V must fit the intended type
// strictly increasing by 1: catches solutions that special-case gaps

Anti-tests worth building explicitly:

• Quicksort killer — if the intended solution sorts with std::sort, an adversarialpermutation can force O(n²) in older libstdc++. Introsort makes this mostly historicalagainst std::sort, but hand-rolled median-of-three sorts remain vulnerable.

• Hash killer — for problems where a solution might use unordered_map with the defaulthash, values all ≡ 0 (mod 2^k) collide catastrophically. If the intended solution doesnot rely on hashing, this test punishes only the shortcut, which is the point.

• Birthday-paradox collisions — for hashing-based string solutions, ~10^5 random stringsof the same length will collide under a 32-bit hash.

5. Strings

rnd.next("[a-z]{100}")             // uniform, alphabet 26  — the easy case
rnd.next("[ab]{100000}")           // alphabet 2  — maximises repeats, borders, periods

Shapes that break string algorithms:

• single character aaaa...a — maximal borders, every suffix a prefix; worst case fornaive matching and for suffix-automaton size

• periodic (abc)^k — long borders, tests period arithmetic

• Fibonacci / Thue–Morse words — maximal number of distinct factors relative to length;classic worst cases for suffix structures and run-detection

• palindrome / near-palindrome — worst case for Manacher and palindromic trees

• one mismatch from periodic — catches solutions that special-case exact periodicity

• all distinct characters where the alphabet allows — the opposite extreme

For "find pattern in text", generate the pattern as a substring of the text half the timeand as a near-miss the other half; uniform random patterns essentially never occur.

6. Geometry

• random points in a box — the easy case

• all collinear — degenerate hull, kills cross-product sign assumptions

• all on a circle — every point on the hull, worst case for hull size

• convex position with many points — same, but not co-circular

• duplicate points — if permitted; catches division by zero and atan2(0,0)

• coordinates at the bound — |x|, |y| ≤ 10^9 means cross products reach 10^18: right atthe long long edge. Generate maximal coordinates deliberately; this is the most commonreal bug in geometry problems.

• three points nearly collinear but not — differing by 1 in one coordinate; catchesepsilon comparisons that should be exact integer arithmetic

7. Queries

If the problem has q operations, the query distribution matters as much as the data:

• uniform random ranges — average length n/3, rarely interesting

• tiny ranges (length 1–2) — maximal overhead per unit of work

• full range every time — catches solutions that rebuild instead of caching

• nested / monotone ranges — worst case for two-pointer and for Mo's ordering

• all queries identical — catches missing memoisation and, conversely, rewards itunfairly, so include the opposite too

• update-heavy vs query-heavy mixes, both extremes, for problems with both

• forced-recompute alternation — update, query, update, query on the same cell

For Mo's-algorithm problems, adversarial query ordering is a real attack: queries chosen tomaximise pointer movement can push a correct O((n+q)√n) solution over the limit, so checkwhether the intended complexity survives.

8. The "max test" is not one test

A single generator invocation at maximum n is not sufficient coverage. Every dimensionshould be maximised both together and separately, because they trade off:

• max n with min values (many collisions)

• max n with max values (overflow)

• max n with max q

• max n with the deepest structure (bamboo, not the bushy default)

• max n with the widest structure (star)

• max total size spread across the maximum number of test cases (t = 10^5, n = 1 each)

• max total size in a single case (t = 1, n = 10^5)

The last two are different tests and routinely catch different bugs: per-case overheadversus per-element overhead. rnd.partition(t, n) builds the split in one call.

9. Turning this into a test plan

A workable default set, in the order worth generating:

1. Samples — hand-written, from the statement, byte-exact.

2. Minimal — n = 1, n = 2, empty where permitted. These find more bugs per test thananything else in the list.

3. Tiny exhaustive — every input with n ≤ 5, if the space is small enough to enumerate.Pairs with a brute-force reference solution for stress testing.

4. Random small — 20–50 tests, so a failure is human-readable.

5. Random large — the default shape at maximum size.

6. Each explicit shape at maximum size — path, star, caterpillar, complete, bipartite,grid, whatever the problem admits.

7. Anti-tests — one per plausible wrong approach or exploitable heuristic.

8. Boundary values — every constraint at its exact bound, and overflow bait.

Name generators after the shape (gen_path.cpp, gen_star.cpp, gen_max.cpp), notgen1.cpp/gen2.cpp, which makes a test plan unreadable six months later. Pass the shape asan option (-type star) when one generator covers several shapes, so the generation scriptdocuments the plan by itself.

10. What to check before shipping

• The validator accepts every generated test — run it, do not reason about it.

• The intended solution is actually slow on the anti-tests, and fast on the rest.

• A brute-force reference agrees with the intended solution on all small tests.

• The maximal tests are genuinely maximal: wc -c them and compare against the constraint.

• Two runs with identical arguments produce identical bytes, and different argumentsproduce different bytes.

How these tests are grouped, scored and proved to discriminate isDesign a testset.