Proving to yourself that a solution is right

Why this matters when you build with AI

An AI assistant will write you a greedy algorithm in ten seconds, with a confident one-paragraph explanation of why it is correct. That explanation is often wrong in a small way: it skips the case where the greedy choice blocks a better choice later. The code will pass the sample in the statement and then fail on the judge.

In a contest you do not have time for a full written proof. You need a short, fast check that tells you whether the idea is worth coding, and a second check that tells you whether the code does what the idea says. This lesson covers both. The first is a small proof habit. The second is a brute force, which is a slow but simple program that is correct by being obvious.

The idea: a claim needs a reason

A solution makes a claim: "this greedy gives the best answer" or "this loop keeps a certain property." A proof is the reason the claim holds for every input, not just the ones you tried.

You do not need a textbook proof. You need one of four habits:

An exchange argument: take any solution that differs from yours, and swap pieces of it, one at a time, until it matches yours without getting worse. If the swap never makes the answer worse, your solution is at least as good as any other.
A loop invariant: a statement that is true before a loop starts, stays true after each pass, and so is true at the end. The invariant has to say what your variables mean, not just what they hold.
Induction on size: show the answer is right for the smallest input, then show that if it is right for size k, it is right for size k+1. In contests this usually means "adding one more item keeps the invariant."
Bounds and overflow checks: write down the largest value each variable can reach, using the limits in the statement, and check that the type can hold it. This is not a proof of correctness, but most wrong answers in practice come from here.

A brute force is the other half. It is a program that tries every possibility, so it is slow and only works for small inputs, but it is hard to get wrong. Two programs that agree on thousands of random small inputs are much more trustworthy than one clever program that you have only read.

In this lesson, "feasible" means that a set of jobs can all be finished on time in some order. "Counterexample" means one small input where your answer is wrong. "Heap" means a priority queue, a container that gives back its largest (or smallest) element quickly. The C++ standard library calls it priority_queue.

Worked example: the bakery queue

The problem

A bakery serves one customer at a time. Customer i needs t minutes of service and must be finished by minute d. The baker starts at minute 0 and may serve the customers in any order. Find the largest number of customers who can be finished on time.

Input: the first line holds n, then n lines each hold t and d. Constraints: n up to 200000, t and d up to 10^14.

This problem has a standard answer, but you should not assume it. The point is to test the habits on a real decision: which customer to drop when the schedule is too full.

Two tempting solutions and the correct one

Here are the two ideas you are most likely to try first.

Idea A: shortest service first. Sort by t. Keep a customer if the total time so far, plus this customer's t, fits before their d. It looks sensible: short jobs fit more customers.

Idea B: earliest deadline first, never drop anyone. Sort by d. Keep a customer if they fit. This is also sensible, because the customer with the earliest deadline is the most urgent.

The correct idea is Idea B with one addition: when the schedule becomes too full, drop the customer with the longest service time. This is the Moore-Hodgson rule, a classic from one-machine scheduling. It is the answer to the question "which customer should I drop?"

The correct solution

// Bakery Queue: maximise the number of customers that finish on time.
// Input: n, then n lines "t d" (service time t, must finish by minute d).
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    cin >> n;
    vector<pair<long long, long long>> jobs(n);  // (deadline d, time t)
    for (auto &[d, t] : jobs) cin >> t >> d;     // input order is t then d
    sort(jobs.begin(), jobs.end());              // earliest deadline first
 
    priority_queue<long long> chosen;            // max-heap of service times
    long long total = 0;                         // sum of times in chosen
    for (auto [d, t] : jobs) {
        chosen.push(t);
        total += t;
        if (total > d) {                         // latest finish is too late
            total -= chosen.top();               // drop the longest job
            chosen.pop();
        }
    }
    cout << chosen.size() << "\n";
    return 0;
}

Compile and run it with the flags the course uses for judging: g++ -O2 -std=c++17 -Wall -Wextra -o correct correct.cpp. Your compiler version will print slightly different warnings or none, but the answers below do not depend on the version.

Proof habit 1: a loop invariant

The invariant for the loop is:

After processing the first i customers (in deadline order), chosen is a feasible set, and its total time is total.

Feasible here means: if you serve the chosen customers in deadline order, each one finishes by its own d. Before the loop, the set is empty, so the invariant holds.

Now the step. Customer i has the largest deadline seen so far, so in deadline order they go last. Their finish time is total_before + t, which is exactly the new total. The set before the step was feasible, so its last finish time, total_before, was at most the deadline of its last customer, which is at most d. So total_before <= d.

If the new total is at most d, the set is still feasible. Nothing else changes, so the invariant holds.
If the new total is more than d, we remove the longest customer, with time m. Since the new customer is one of the chosen ones, m >= t. The new total is total - m, which is at most total - t = total_before <= d. So the set is feasible again.

Both branches keep the invariant. That is the whole feasibility proof, and it takes five lines to write.

Proof habit 2: the exchange argument for optimality

Feasibility only says the answer is achievable. Optimality says nothing better exists. The standard argument is an exchange: take any feasible set of customers that is larger than the one the algorithm holds, and show that swapping customers one at a time turns it into the algorithm's set without losing size.

The heart of that argument is the drop step. When the algorithm removes the longest customer, that customer is the one whose removal leaves the smallest total time for the set. A set with a smaller total is easier to extend later, so no later customer is lost because of the drop. The full argument is in J. M. Moore's 1968 paper in Management Science on minimising the number of late jobs on one machine, where the rule comes from. I did not reproduce that proof here. What I did was test the claim on 500 random small inputs, described below.

Proof habit 3: check the bounds and types

The statement says t and d go up to 10^14, and n up to 200000. The total time can reach 200000 * 10^14 = 2 * 10^19 if you add everything, which is larger than a 64-bit signed integer can hold. The code keeps only the chosen customers in total, so the sum is at most the largest deadline, about 10^14. That fits in long long. The point is to write this bound down before you submit, not to notice it after a wrong verdict.

Test against brute force

The brute force below tries every subset of customers and every order of each subset. It is fine for n up to 7. It does not use any idea from the algorithm, so if it agrees with your code, the agreement means something.

// Brute force for small n (n <= 7): try every subset and every order of it.
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    vector<long long> t(n), d(n);
    for (int i = 0; i < n; i++) cin >> t[i] >> d[i];
 
    int best = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        int size = __builtin_popcount(mask);
        if (size <= best) continue;
        vector<int> order;
        for (int i = 0; i < n; i++)
            if (mask >> i & 1) order.push_back(i);
        bool ok_any = false;
        do {
            long long finish = 0;
            bool ok = true;
            for (int i : order) {
                finish += t[i];
                if (finish > d[i]) { ok = false; break; }
            }
            if (ok) { ok_any = true; break; }
        } while (next_permutation(order.begin(), order.end()));
        if (ok_any) best = size;
    }
    cout << best << "\n";
    return 0;
}

I ran the three candidates against this brute force on 500 random inputs. The generator picks n from 1 to 6, t from 1 to 5, and d from 1 to 12. Here are the real results:

correct: 0 mismatches out of 500
wrong_a: 82 mismatches out of 500 (seed 9: want 3 got 2)
wrong_b: 5 mismatches out of 500 (seed 29: want 3 got 2)

The brute force is the reason I trust the correct solution more than the two wrong ones. Idea A and Idea B both look right when you read them. The brute force finds the flaw in both within the first few dozen tests, and gives you a small input to read by hand.

Find the counterexamples

Idea A fails on this input, which has two customers:

2
1 3
2 2

Here the first number is t and the second is d. Idea A sorts by t, so it takes the customer with t = 1 first, and total becomes 1. The second customer needs t = 2, so total would be 3, which is more than d = 2. It is skipped. The answer is 1.

The correct answer is 2: serve the customer with t = 2, d = 2 first (finish at minute 2, on time), then the other one (finish at minute 3, which is not more than its d = 3). Idea A blocked the urgent customer by serving a longer-deadline one first.

Idea B fails on this input, which has three customers:

Idea B sorts by d, so it looks at the customer with t = 3, d = 3 first and takes them, total becomes 3. The next two customers each need t = 2, so total would be 5, which is more than their d = 4. Both are skipped. The answer is 1.

The brute force and the correct solution both give 2: serve the two t = 2 customers, finishing at minutes 2 and 4. The long customer with d = 3 blocks both of them, because Idea B has no way to undo a choice. The correct solution handles it: it sorts the customers as (3,3), (2,4), (2,4), takes the first, then sees total 5 after the second, which is more than 4, so it drops the longest one, the t = 3 customer. The third customer then fits, and the answer is 2.

I ran both inputs through the programs. The first input (the two-customer case above) printed:

brute=2 correct=2 wrong_a=1 wrong_b=2

The second input (the three-customer case) printed:

brute=2 correct=2 wrong_a=2 wrong_b=1

Idea A fails on the first input and Idea B passes it. Idea B fails on the second input and Idea A passes it. The two inputs break different ideas, which is why you need both.

Overflow check

To see a bounds failure, use a version of the correct code with int in place of long long:

input: 3 / 1000000000 2000000000 (three lines, all the same)
long long version: 2
int version: 3
brute: 2

With three customers of time 10^9 and deadline 2 * 10^9, the running total reaches 3 * 10^9. That is larger than the largest int (about 2.1 * 10^9), so the int version overflows, the check total > d never fires, and it keeps all three customers. Signed overflow is undefined behaviour in C++, so the wrong number here is what this compiler produced. A different compiler may print a different wrong number, or the right one by luck. Both are bad news for you.

Complexity

Sorting costs O(n log n), and each customer is pushed and popped from the heap at most once, which costs O(n log n) in total. On my machine (WSL2, g++ 15.2, -O2), a random input with n = 200000, times up to 10^9 and deadlines up to 10^14, ran in 0.05 seconds.

Common mistakes

Trusting a sample. The sample in the statement often has only two or three customers, and many wrong ideas give the right answer on it. The sample above gives 2 for all four programs. Always run the brute force on small random inputs before you submit.

A proof that skips the hard step. A common version: "the greedy is optimal because it picks the best choice each time." The proof needs to say which choice is best and why taking it never hurts later. If you cannot write the exchange, the idea is not proven yet.

Using int for a sum. The symptom is an answer that is too large, or a verdict that changes when you change the order of the input. Write down the largest value of each variable, using the limits, before you pick the type.

Confusing feasible with maximal. The loop invariant says the set is feasible. It does not say the set is the largest possible. Keep the two claims separate in your notes, or you will assume the invariant gives you more than it does.

Reading an AI proof as a proof. AI tools produce fluent proofs for wrong ideas, and they often say "by an exchange argument" without writing the exchange. When an AI gives you a proof, ask it for a counterexample to each step, then run the brute force. If the brute force disagrees, the proof is wrong, whatever the text says.

Hands-on exercise

Use the programs and inputs in this lesson. You can copy the C++ code from the sections above, or write your own. Each exercise has an answer under "Show the answer".

Exercise 1: trace by hand

Trace the correct solution on this input, by hand, without running it. Write down the sorted order, the heap after each push and pop, and the final answer.

Check your answer by running the correct solution on the same input.

Show the answer

Sorted by deadline, the pairs (d, t) are (3,3), (4,2), (5,4), (7,1).

Push 3. Total is 3, which is at most 3. Heap is {3}.
Push 2. Total is 5, which is more than 4. Remove the top, 3. Total is 2. Heap is {2}.
Push 4. Total is 6, which is more than 5. Remove the top, 4. Total is 2. Heap is {2}.
Push 1. Total is 3, which is at most 7. Heap is {2, 1}.

The final heap has two elements, so the output is 2. The brute force also prints 2.

Exercise 2: find a counterexample to Idea A

Find a two-customer input on which Idea A (shortest service first) gives a smaller answer than the correct solution. The smaller the numbers, the better.

Show the answer

One input is 2 / 1 3 / 2 2, shown above. Idea A prints 1, and the correct solution and the brute force print 2. Any input where the short customer has a late deadline and the long customer has an early deadline also breaks Idea A.

Exercise 3: write a five-line feasibility proof

Write five lines that prove the loop invariant "the chosen set is always feasible" for the correct solution. Use only the facts in the code. You may use the words "before the step" and "after the step".

Show the answer

Before each step, the chosen set is feasible, and its total is at most the deadline of its last customer.
The new customer has the largest deadline so far, so in deadline order they are last.
If the new total is at most d, the set is still feasible.
If the new total is more than d, the removed customer has time at least t, so the new total is at most the old total, which is at most d.
Both cases keep the set feasible, so the invariant holds at the end of the loop.

A good answer is short and says which fact about the order is used in each line. A weak answer says "it works because the greedy is correct" and gives no step.

Exercise 4: find the overflow input

The int version above gives the wrong answer on one specific three-customer input. Write an input with two customers, with times and deadlines in the int range, where the int version prints a wrong answer. Check your input against the long long version and the brute force.

Show the answer

Two customers with time 2 * 10^9 are not allowed, because the input value itself does not fit an int. Use three customers with time 10^9 and deadline 2 * 10^9, as in the section above. The int version prints 3, and the correct answer is 2. Any input where the running total passes the int limit while every deadline is still in range shows the same bug.

Exercise 5: check an AI proof

Ask an AI assistant to prove that Idea B (earliest deadline first, never drop anyone) is optimal for this problem. Use this prompt:

Here is a scheduling problem. Customer i needs t_i minutes and must finish by d_i.
One server, customers served in any order from minute 0. Maximise the number served on time.
Claim: sorting by deadline and keeping each customer who fits is optimal.
Give a proof. For each step of the proof, say which fact it uses.
If the claim is false, give the smallest counterexample you can find.

A good answer either proves the claim (and you then check each step) or gives a counterexample with numbers. Check it: run the brute force on the counterexample. A bad answer gives a proof with a step like "by an exchange argument" and no swap. Note the result in one line: did the AI find the d = 3 blocking case, or did it miss it?

Show the answer

The claim is false. Idea B gives 1 on 3 / 2 4 / 2 4 / 3 3, and the answer is 2. Any answer that says the claim is true is wrong, and a proof for it must have a gap at the step where a long customer is kept.

Checklist

Write the claim in one sentence before you code the idea.
Write a loop invariant that says what each variable means.
Check the largest value of each variable against the limits, and the type it is stored in.
Find a counterexample to the idea on paper, with two or three items, before you code it.
Write a brute force that does not use the idea, and run both on 500 random small inputs.
Keep the counterexample that broke the last wrong idea, and run it again after each change.
Never submit on the strength of a proof you have not checked step by step.

Summary

A proof in a contest is a short, honest reason for your claim: an invariant that holds through the loop, an exchange argument for optimality, or an induction on the size of the input. Pair it with a brute force, because a brute force catches a wrong idea that a proof written by you or an AI would hide. The bakery queue shows both habits working together: two plausible ideas fail on three-customer inputs, and the correct one passes 500 random tests.