Building a Brute-Force Oracle for Small-Input Verification

Welcome back. In the previous lesson, you used induction to make a recursive algorithm’s contract precise: define exactly what every call must return, establish base cases, and justify how smaller correct results combine. A brute-force oracle needs the same discipline. It is only useful if its contract matches the statement exactly.

This lesson shifts from proving an algorithm on paper to building a deliberately slow implementation that can serve as a source of truth on small inputs. The goal is not to submit it. The goal is to compare it with a faster solution and turn a vague “my code ought to work” into a concrete, checkable claim.

---

What makes a brute-force program an oracle?

A brute-force solution systematically examines every relevant candidate in a problem’s search space. An oracle is a trusted implementation whose output you use as the expected answer when checking another implementation.

Those terms overlap, but the second word is the important one here: a slow program is not automatically an oracle. It becomes one only when it faithfully implements the specification.

For a single test case $x$, imagine two functions:

$$B(x)=\text{answer returned by the brute-force oracle}$$ $$F(x)=\text{answer returned by the fast solution}$$

A comparison checks whether

$$B(x)=F(x).$$

If they differ, at least one component is wrong:

• the fast algorithm or its implementation;
• the brute-force oracle;
• the interpretation of the statement;
• occasionally, the output comparison itself.

If they agree on many cases, that is strong evidence, not a proof, that the fast code is correct. The proof still comes from the reasoning you developed in earlier lessons. The oracle is a highly effective way to detect that the implemented code is not the algorithm you proved.

The central design principle is:

Make the oracle simpler and structurally different from the optimized solution, even if it is dramatically slower.

For example, if the fast solution uses dynamic programming, a good oracle might enumerate all subsets. If the fast solution uses sorting and two pointers, the oracle might inspect every pair directly. Reusing the fast algorithm’s clever condition inside the brute program defeats the point: the same mistaken idea can appear in both.

---

Start with the search space, not with loops

Before writing code, identify the objects that could constitute an answer. This collection is the search space.

Most brute-force oracles follow the same four-part model:

1. Candidate representation: What data represents one possible answer?
2. Enumeration: How will the program generate every candidate?
3. Feasibility test: How will it determine whether a candidate obeys every rule?
4. Aggregation: What does it do with valid candidates: count them, minimize a value, maximize a value, or retain one witness?

Here are common search spaces worth recognizing quickly:

Problem asks for…	Natural candidate space	Usual enumeration
A pair satisfying a condition	Ordered or unordered index pairs	Two loops
A contiguous segment	All endpoint pairs $(l,r)$	Two loops
A subset of $n$ indexed items	All $2^n$ masks	Bitmask loop or recursion
An arrangement	All permutations	next_permutation or backtracking
A string over a small alphabet	All strings of a fixed length	Recursive construction
A graph choice	Often subsets of edges or vertices	Bitmasks on very small graphs

The word all is doing the logical work. If you forget a category of candidate, the program may be slow but still wrong.

There is also a distinction that prevents many flawed “brute-force” solutions:

• The search space consists of possible answers.
• The feasibility predicate checks whether a candidate satisfies the problem constraints.
• The objective function assigns a value to a feasible candidate in an optimization problem.

For instance, in knapsack, “all subsets of items” is the search space. “Total weight does not exceed capacity” is feasibility. “Total value” is the objective. Keeping these separate makes the oracle much easier to audit.

---

A worked oracle: maximum-weight nonadjacent subset

Use the path problem from the previous lesson. Given weights

$$w_0,w_1,\dots ,w_{n-1},$$

select a subset of positions with no adjacent selected positions, maximizing total weight. Selecting nothing is allowed.

The optimized recurrence was

$$D[i]=\max (D[i-1],D[i-2]+w_i).$$

That is exactly the kind of logic the oracle should not repeat. Instead, enumerate every subset of positions.

Formal specification

The feasible family is

$$\mathcal{F}=\left\{S\subseteq \{0,\dots ,n-1\}\mid \text{no adjacent indices both belong to }S\right\}.$$

The required value is

$$\underset{S\in \mathcal{F}}{\max }\sum _{i\in S}{w}_i.$$

A mask from $0$ through $2^n-1$ naturally represents a subset:

• bit $i$ is $1$ if position $i$ is selected;
• bit $i$ is $0$ otherwise.

For stress testing, keep $n$ small, such as $n\le 18$. The oracle then performs at most about

$$18\cdot 2^{18}$$

basic checks per test case, which is entirely reasonable in C++.

using ll = long long;

ll bruteNonAdjacent(const vector<ll>& w) {
    int n = (int)w.size();
    ll best = 0;  // Empty subset is allowed.

    for (ll mask = 0; mask < (1LL << n); ++mask) {
        bool valid = true;
        ll sum = 0;

        for (int i = 0; i < n; ++i) {
            if ((mask & (1LL << i)) == 0) continue;

            // Selecting i and i - 1 is forbidden.
            if (i > 0 && (mask & (1LL << (i - 1)))) {
                valid = false;
                break;
            }

            sum += w[i];
        }

        if (valid) {
            best = max(best, sum);
        }
    }

    return best;
}

This code intentionally does not optimize away invalid masks, precompute transitions, or reproduce the dynamic program. Clarity is more valuable than speed.

Why this oracle is correct

Its proof has the same shape as a correctness proof for any algorithm.

Coverage. Every subset $S$ of the $n$ positions has a unique binary mask: bit $i$ is set exactly when $i\in S$. Therefore, looping over all masks examines every possible subset exactly once.

Feasibility. The code rejects a mask precisely when it contains two consecutive set bits. That is exactly the rule prohibiting adjacent selected positions. Thus the masks accepted by valid are exactly the feasible subsets in $\mathcal{F}$.

Objective evaluation. For every valid mask, the code adds exactly the weights of its selected positions. So sum is the objective value of that candidate.

Aggregation. best is the maximum objective value among every valid mask processed so far. After all masks have been processed, it is the maximum over all feasible subsets, which is the required answer.

Notice the difference from an optimized proof. The optimized recurrence had to justify a subtle claim about all optimal solutions splitting into two cases. The brute-force proof is almost tautological: it checks every candidate defined by the problem.

That is why a brute-force oracle is so useful.

Boundary semantics matter

The initialization

ll best = 0;

is correct only because selecting nothing is allowed. If the statement required selecting at least one position, then an all-negative array would need a negative answer. In that version, initialize best to a value below every achievable sum, such as LLONG_MIN, and ensure at least one item is selected.

A brute-force program can be wrong through a tiny interpretation error just as easily as a fast program can. Always write down the edge-case semantics before coding.

Useful manual sanity cases for this oracle are:

Weights	Correct result	Reason
$[5]$	$5$	Select the only item.
$[-5]$	$0$	The empty subset is better.
$[5,4]$	$5$	The two positions are adjacent.
$[5,100,5]$	$100$	The middle value dominates.
$[5,-100,5]$	$10$	Select both endpoints.

These cases check the specification before you rely on the oracle to diagnose something else.

---

Enumerating candidates without accidentally solving the fast problem

The enumeration method should match the search space, but it should remain direct.

Subarrays

For a maximum-subarray oracle, enumerate every pair of endpoints. A clear $\mathcal{O}(n^3)$ oracle sums each subarray directly; a slightly cleaner $\mathcal{O}(n^2)$ version accumulates the sum while extending its right endpoint.

ll bruteMaxSubarray(const vector<ll>& a) {
    ll best = LLONG_MIN;
    int n = (int)a.size();

    for (int l = 0; l < n; ++l) {
        ll sum = 0;
        for (int r = l; r < n; ++r) {
            sum += a[r];
            best = max(best, sum);
        }
    }

    return best;
}

This is still plainly brute force: it examines every subarray. Reusing a running sum does not reduce the candidate space; it merely evaluates each candidate’s value more conveniently.

Subsets

For $n$ small indexed elements, a bitmask is often the most reliable representation:

for (int mask = 0; mask < (1 << n); ++mask) {
    // Interpret the bits of mask as a subset.
}

Use 1LL << n when $n$ may reach the range where an int shift becomes unsafe. For a stress oracle, do not push $n$ near the machine-word limit anyway; the exponential enumeration would already be impractical.

Permutations and constructed strings

When the candidate is an ordering, generate all orderings. When the candidate is a length-$n$ string over an alphabet, recursively choose one character at each position until the candidate is complete.

The relevant invariant for a recursive generator is simple:

At recursion depth $p$, the first $p$ decisions of the candidate have been fixed, and every possible completion of that prefix will be explored exactly once.

This is the same “recursive calls cover all smaller valid cases” mindset from the last lesson, now applied to enumeration rather than an optimized divide-and-conquer algorithm.

---

Keep the oracle independent

The practical rule is not “never reuse a line of code.” Reading input and storing the same array is unavoidable. The rule is:

Do not reuse the fast solution’s critical decision logic, transformations, or assumptions.

Here are common ways an oracle becomes untrustworthy:

Mistake	Why it is dangerous	Better approach
Copying the optimized feasibility condition	Both programs can share the same logical flaw.	Re-derive feasibility directly from the statement.
Implementing a “simpler greedy” rather than exhaustive search	A greedy method is not automatically correct.	Enumerate all candidates on small input.
Skipping candidates that “obviously cannot win”	The shortcut may be the bug.	Avoid pruning unless its safety is trivial and proved.
Sorting or modifying the input unnecessarily	It may destroy position-dependent meaning.	Preserve the original structure unless the statement permits transformation.
Mishandling duplicate values	Values may be equal even when indices are distinct.	Enumerate indexed candidates, not merely distinct values.
Ignoring output semantics	Equal objective values may correspond to different valid witnesses.	Compare what the judge actually requires.

The last row deserves care. If a problem asks only for an optimal value, compare values. If it asks for a witness, the oracle may return a valid witness and its objective value, while a separate checker verifies that the fast program’s witness is valid and equally good.

If multiple outputs are valid and the judge accepts any one of them, raw text comparison can be misleading. For example, two different optimal subsets may both be correct even though their printed indices differ. In that setting, compare normalized answers or validate both outputs against the specification.

---

A compact oracle-design protocol

When you are stuck after coding a likely-correct $1600+$ solution, use this protocol before trying random edits.

1. Freeze the exact contract.
   State the input, required output, whether empty choices are allowed, and all special cases.

2. Name the search space.
   Write a sentence such as “all subarrays,” “all subsets of vertices,” or “all permutations of the indices.”

3. Choose a representation.
   Use endpoints for segments, masks for subsets, and a recursive partial construction for sequences or strings.

4. Write a direct feasibility checker.
   Translate every constraint in the statement into a clear condition. Do not use the fast solution’s key observation.

5. Evaluate and aggregate.
   For each valid candidate, count it, minimize it, maximize it, or save it according to the statement.

6. Set deliberately tiny oracle bounds.
   The original problem may allow $n=2\cdot 10^5$, while your checker might use $n\le 15$. That is expected: the fast solution must handle full constraints; the oracle only needs to expose incorrect behavior on small legal cases.

7. Test the oracle on hand-checkable cases.
   Include minimum sizes, duplicates where permitted, all equal values, negative values where permitted, and cases where the best answer lies at a boundary.

A useful pre-coding note might look like this:

Candidates: all subsets of positions.
Representation: a bitmask of length $n$.
Valid iff: no two consecutive bits are set.
Value: sum of selected weights.
Answer: maximum value among valid masks.
Oracle limit: $n\le 18$.

This takes less than a minute to write, but it catches many modeling mistakes before they become a difficult Wrong Answer.

---

Takeaways

A brute-force oracle is an exhaustive, specification-first implementation used to check a faster solution on small legal inputs.

The reliable construction process is:

• identify the complete search space;
• enumerate every candidate;
• test feasibility directly from the statement;
• evaluate valid candidates and aggregate the required result;
• keep the oracle’s core logic independent from the optimized approach;
• validate the oracle itself on tiny cases whose answers you can determine by hand.

The brute-force proof is usually short because it rests on exhaustive coverage: every valid answer candidate is considered, and the best or required one is selected.

Next, you will connect this oracle to a randomized test generator and a comparison loop, so that a mismatch automatically produces a concrete failing input for investigation.