The essence of algorithmic competitions lies in the combination of mathematical modeling and engineering implementation. Intuition can guide the direction of problem-solving, but it cannot guarantee the correctness of an algorithm under all extreme data conditions. Especially in greedy algorithms, game theory, and construction problems, a submission lacking rigorous proof is no different from blind trial and error. Mastering core proof techniques not only improves the first-attempt acceptance rate but also breaks through mental bottlenecks.
Below are the four most essential proof techniques in competitive programming.
Adjacent Exchange Method
This is the most mechanized proof model in greedy algorithms. When you suspect that the optimal solution may depend on some sorting rule but cannot be intuitively certain, you assume the existence of an optimal sequence, swap two adjacent elements in it, and derive the condition under which the answer becomes worse or unchanged after the swap. By working backwards, you deduce the partial order relation that the sorting must satisfy.
The operational paradigm lies in stripping away the global context and focusing only on the local micro-element. Let the total cost be the objective function. Extract the $i$-th and $i+1$-th items from the sequence, write out the local objective function expressions before and after the swap, set the pre-swap state to be better than the post-swap state, simplify the inequality, and the resulting expression becomes the logic for overloading the sorting operator.
Proof by Contradiction and the Replacement Principle
When a problem requires proving that a locally optimal choice must be included in the globally optimal solution, proof by contradiction is the best entry point. This is often referred to as the "optimal solution replacement theorem."
We assume that the globally optimal solution does not contain the choice made by our current greedy strategy. Then, starting from that assumed optimal solution, we attempt to replace some element in the optimal solution with the element chosen by our greedy strategy. If we can prove that the cost of the new solution after replacement is less than or equal to that of the original solution, this either contradicts the premise that the original solution was optimal, or demonstrates that our greedy choice can also achieve optimality.
Monotone Quantities and Invariant Analysis
When dealing with board games, state transitions, or simulation problems involving cyclic operations, identifying invariants or strictly monotone quantities in the state transition system is the key to solving the problem.
If the problem asks whether a certain state is reachable, look for invariants. If the invariant of the initial state differs from that of the target state, then the target state is absolutely unreachable. If the problem asks to prove that a process must terminate, look for a monotone quantity. As long as you can define a potential function that strictly decreases with every operation and has a lower bound, you can mathematically prove that the program cannot fall into an infinite loop, and you can also use it to evaluate the time complexity.
Mathematical Induction
This is primarily used for proving the correctness of dynamic programming and for construction problems. It reduces the problem size $N$ to the known state of size $N-1$. In competitive programming, mathematical induction is not merely a proof tool; it is also a mental scaffold for directly deriving recurrence relations or recursive equations. By establishing the boundary conditions and proving that if the proposition holds for size $K$, it must hold for size $K+1$, you confirm that the state transition network forms a valid directed acyclic graph.
To concretely demonstrate how these techniques are applied in practice, we use the adjacent exchange method to solve a classic problem.
Classic Problem Analysis
Problem Statement There are $N$ cows that need to form a tower. The $i$-th cow has weight $W_i$ and strength $S_i$. The risk value of each cow is defined as the total weight of all cows above it minus its own strength. Determine an ordering such that the maximum risk value among the $N$ cows is minimized.
Solution Approach Assume that the current sequence is already the optimal ordering that minimizes the maximum risk value. Consider any two adjacent cows at positions $i$ and $i+1$. Let the total weight of all cows above them be $P$.
For these two cows, before the swap: The risk value of the cow at position $i$ is $P - S_i$. The risk value of the cow at position $i+1$ is $P + W_i - S_{i+1}$. The maximum risk value between the two is $\max(P - S_i, P + W_i - S_{i+1})$.
After swapping these two cows: The risk value of the former cow at position $i+1$ becomes $P - S_{i+1}$. The risk value of the former cow at position $i$ becomes $P + W_{i+1} - S_i$. The maximum risk value after the swap is $\max(P - S_{i+1}, P + W_{i+1} - S_i)$.
To ensure that the pre-swap state is no worse than the post-swap state, the maximum risk value before the swap must be less than or equal to that after the swap. Since $P - S_i$ is strictly less than $P + W_{i+1} - S_i$, and similarly $P - S_{i+1}$ is strictly less than $P + W_i - S_{i+1}$, the deciding factor between the two maxima lies in the cross terms.
Set $P + W_i - S_{i+1} < P + W_{i+1} - S_i$. After simplification, we obtain $W_i + S_i < W_{i+1} + S_{i+1}$.
The conclusion is remarkably clear: sort the cows in ascending order of $W+S$, and the globally optimal solution is obtained.
Core Code
struct Cow {
long long w, s;
bool operator<(const Cow& other) const {
return w + s < other.w + other.s;
}
};
Complete Code
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const long long INF = 1e18;
struct Cow {
long long w, s;
bool operator<(const Cow& other) const {
return w + s < other.w + other.s;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<Cow> cows(n);
for (int i = 0; i < n; ++i) {
cin >> cows[i].w >> cows[i].s;
}
sort(cows.begin(), cows.end());
long long sum_w = 0;
long long ans = -INF;
for (int i = 0; i < n; ++i) {
ans = max(ans, sum_w - cows[i].s);
sum_w += cows[i].w;
}
cout << ans << "\n";
return 0;
}