Why this matters when you build with AI
AI tools write working-looking code very fast. They also write code that passes the one example you showed them and fails on the next input. The difference between a useful result and a confident wrong one is a check you run before you trust the output.
A round at this level teaches two checks that carry over. The first is a time budget with a skip rule, so one stuck task does not eat the time for the others. The second is a stress test: a generator makes many small random inputs, a slow but simple brute force gives the answer, and a script compares the two. The stress test is cheap to write and it catches the bugs that a sample input hides.
Words used in this lesson
A two pointers method keeps two indices into a sorted array and moves them in one direction each, so the whole scan takes linear time after the sort.
Binary search on the answer works when a yes-or-no question about a number x is monotone: once the answer is yes for some x, it stays yes for every larger x. You then search for the smallest yes.
A BFS (breadth-first search) on a grid visits cells in rings of increasing distance from the start. It gives shortest step counts when every step costs the same.
A DFS (depth-first search) on a grid goes as deep as it can before it backtracks. It finds connected regions, but it does not give shortest paths.
Dynamic programming (DP) stores the answer to small subproblems in a table, and builds larger answers from them. A state is what one table entry means. A transition is the rule that computes one entry from earlier entries.
A brute force is a slow program that is easy to trust, for example one that checks every pair. A stress test runs the brute force and your fast solution on many random small inputs and compares the outputs.
An O(n^2) trap is a loop nest that looks correct and passes the sample, but takes about n times n steps. With n equal to 200000, n times n is 4 * 10^10, which is far beyond what a 5-second limit allows. The judge gives 5 seconds of wall-clock time for each test, as the site judge lesson explains.
A budget is the number of minutes you allow yourself on a problem. A skip rule says what to do when the budget ends.
The idea: a fixed budget and a skip rule
This round has five problems and a total of 100 minutes. Divide the time evenly: 20 minutes per problem. Leave the last few minutes for stress tests and the final submission.
The skip rule is the part most people do not follow:
- If you have no new idea for 10 minutes, write one line about what you tried and move to the next problem.
- When a problem reaches its 20-minute budget without an accepted submission, stop. Write the line, and move on.
- Come back to a skipped problem only after the other four are either accepted or skipped, and only if time is left.
The point is not that you should never think longer. The point is that the decision to continue must be made on purpose, with the other problems in view, and not because you have already spent 40 minutes and do not want to admit it. The time-per-problem lesson in the contest strategy module explains sunk cost in full.
Here is a log line that works:
problem C (grid shortest path): skipped at 20 min. Tried BFS from both ends,
then DFS. Suspect the walls are not read correctly; not checked yet.Two-pointer example, traced by hand
Before the round, here is the two pointers idea on a tiny array. Take the sorted values 1 2 4 6 and the limit S = 7. Count the pairs of positions i < j with a[i] + a[j] <= 7.
Start with l at the first position and r at the last. If a[l] + a[r] <= S, then every value between l + 1 and r also pairs with a[l], because the values are sorted and they are all at most a[r]. So you add r - l pairs and move l right. Otherwise a[r] is too big even with the smallest value, so you move r left.
l r a[l] + a[r] action count
0 3 1 + 6 = 7 7 <= 7, add r - l = 3, l++ 3
1 3 2 + 6 = 8 8 > 7, r-- 3
1 2 2 + 4 = 6 6 <= 7, add r - l = 1, l++ 4
2 2 stop, l is not less than r 4The pairs are (1,2), (1,4), (1,6) and (2,4). That is 4 pairs, the answer from the table.
The standard technique: stress testing before you submit
A stress test has three parts: a generator, a brute force and a comparison. Write all three in a single Python file. Python is fast enough for this, because the brute force and the generator only need to handle small inputs.
Here is a complete stress test for problem A of this round. The solution is in the next section. It makes 300 random inputs with n up to 8 and values up to 10, and it compares the solution with a brute force that checks every pair.
import random
import subprocess
import sys
SOLUTION = sys.argv[1]
TRIALS = int(sys.argv[2]) if len(sys.argv) > 2 else 300
SEED = 7
def make_case(rng):
n = rng.randint(1, 8)
S = rng.randint(0, 20)
values = [rng.randint(0, 10) for _ in range(n)]
text = f"{n} {S}\n" + " ".join(map(str, values)) + "\n"
return text, n, S, values
def brute(n, S, values):
count = 0
for i in range(n):
for j in range(i + 1, n):
if values[i] + values[j] <= S:
count += 1
return count
rng = random.Random(SEED)
for trial in range(TRIALS):
text, n, S, values = make_case(rng)
expected = brute(n, S, values)
run = subprocess.run([SOLUTION], input=text, capture_output=True, text=True, timeout=5)
got = run.stdout.strip()
if got != str(expected):
print(f"mismatch on test {trial}")
print("input:")
print(text, end="")
print(f"expected {expected}, got {got}")
sys.exit(1)
print(f"{TRIALS} random tests passed")Run it from the folder that holds your compiled solution. The stress script takes the path of the program as its first argument. Compile the solution first:
g++ -std=c++17 -O2 -o pairs pairs.cpp && python3 -I stress.py ./pairs 300On a correct solution, the last line is:
300 random tests passedUse python3 -I so that a file in your current folder cannot shadow a standard library module.
Now the same stress script on a wrong version of the solution. The only change is < in place of <=, which means a pair whose sum is exactly S is not counted. The line is if (a[l] + a[r] < S) {. The stress test catches it at once:
mismatch on test 2
input:
7 2
3 1 8 6 0 9 1
expected 3, got 2A random test with small values hits boundary cases like this often, and it found this one on the third trial. Writing the stress test takes a few minutes, and it covers far more cases than a hand-made sample.
Worked example: the square root by binary search
This example is not one of the round problems. It shows the binary search skeleton on the answer.
Statement. The first line has t, the number of questions, with 1 <= t <= 1000. Each of the next t lines has an integer N with 0 <= N <= 10^18. For each N, print the largest integer x such that x * x <= N.
Sample input:
3
0
10
17Sample output:
0
3
4The idea. The predicate "x * x <= N" is monotone: if it holds for x, it holds for every smaller x. So the answer is the last x where it holds. Start with lo = 0, which always holds, and hi = 10^9, which is the largest possible answer for N up to 10^18. Take the middle mid, rounding up so that the loop always makes progress. If mid * mid <= N, the answer is at least mid, so lo = mid. Otherwise the answer is below mid, so hi = mid - 1.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
long long N;
cin >> N;
long long lo = 0, hi = 1000000000LL;
while (lo < hi) {
long long mid = (lo + hi + 1) / 2;
if (mid * mid <= N) lo = mid;
else hi = mid - 1;
}
cout << lo << "\n";
}
}Compile and run on the sample:
g++ -std=c++17 -O2 -o sqrt sqrt.cpp && printf '3\n0\n10\n17\n' | ./sqrtThe output is:
0
3
4I checked this program on 500 random inputs of 20 values each, with N up to 2000, against a Python brute force that counts up from 0. I also checked 508 values with N up to 10^18, including 10^18, 10^18 - 1 and squares and their neighbours, against Python's math.isqrt. All of them agreed.
Complexity. The loop runs about 30 times, because the range is 10^9. Each step is constant work. The total time is O(log C) per question, where C is the range of the answer.
Pitfalls. Use mid = (lo + hi + 1) / 2. With mid = (lo + hi) / 2 and lo = mid, the loop can run forever when hi = lo + 1. The mid * mid product must fit in the type: with hi set to 10^9 it fits in long long, but with hi set to 10^18 it does not.
The round: five problems
Set a 100-minute timer and use the budget from the idea section. Each problem has a statement, a sample and a limit. The editorial sits under the line Show the answer, and you should open it only after you have submitted or after your budget for the problem has ended.
For every problem, write a stress test before you submit. The generator must produce inputs that are small enough for the brute force, and the brute force must be simple enough that you trust it without debugging it.
Problem A: pairs under a limit
You are given n numbers and a limit S. Count the pairs of positions i < j such that the sum of the two numbers is at most S.
Limits: 1 <= n <= 200000, each number between 0 and 10^9, and 0 <= S <= 2 * 10^9. The answer can be larger than 2^31, so use a 64-bit type.
Input: the first line holds n and S. The second line holds the n numbers.
Sample input:
5 6
4 1 3 2 5Sample output:
6Show the answer
Sort the numbers. Use two pointers, l at the smallest value and r at the largest. If a[l] + a[r] <= S, every position from l + 1 to r pairs with l, so add r - l and move l right. Otherwise move r left.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long S;
cin >> n >> S;
vector<long long> a(n);
for (auto &x : a) cin >> x;
sort(a.begin(), a.end());
long long count = 0;
int l = 0, r = n - 1;
while (l < r) {
if (a[l] + a[r] <= S) {
count += r - l;
l++;
} else {
r--;
}
}
cout << count << "\n";
}The sample gives 6. The sorted sample is 1 2 3 4 5, and the six pairs are (1,2), (1,3), (1,4), (1,5), (2,3) and (2,4). The sort takes O(n log n), and the scan takes O(n). I checked the program with a stress test against an all-pairs brute force on 500 random inputs, and all agreed.
Intended complexity: O(n log n).
O(n^2) trap: a double loop over all pairs. It passes the sample, but for n equal to 200000 it checks about 2 * 10^10 pairs, which is far beyond the time limit.
Problem B: sprinklers on a line
Flowers grow at n integer positions on a line. You may place k sprinklers at any integer positions. A sprinkler at position p waters every flower at distance at most r from p. Find the smallest integer r such that k sprinklers can water every flower.
Limits: 1 <= k <= n <= 200000, each position between 0 and 10^9. Positions may repeat.
Input: the first line holds n and k. The second line holds the n positions.
Sample input:
5 2
1 2 9 10 11Sample output:
1Show the answer
Binary search on r. For a fixed r, the check is greedy: take the leftmost unwatered flower at position x. Put a sprinkler at x + r, which waters everything in [x, x + 2r]. Skip those flowers and repeat. If you need at most k sprinklers, r works. The check is monotone: a larger r never needs more sprinklers. So the smallest working r is found by binary search from 0 to the spread of the positions.
#include <bits/stdc++.h>
using namespace std;
int n;
long long k;
vector<long long> x;
bool enough(long long r) {
long long used = 0;
int i = 0;
while (i < n) {
used++;
if (used > k) return false;
long long reach = x[i] + 2 * r;
i = upper_bound(x.begin(), x.end(), reach) - x.begin();
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
x.resize(n);
for (auto &v : x) cin >> v;
sort(x.begin(), x.end());
long long lo = 0, hi = x[n - 1] - x[0];
while (lo < hi) {
long long mid = (lo + hi) / 2;
if (enough(mid)) hi = mid;
else lo = mid + 1;
}
cout << lo << "\n";
}On the sample, r = 1 works: the first sprinkler at 2 waters 1 and 2, and the second at 10 waters 9, 10 and 11. r = 0 would need five sprinklers. The program prints 1. I checked it with a stress test against a brute force that tries every set of at most k positions in a window around the flowers, for r from 0 upward, on 500 random small inputs. All agreed.
Intended complexity: O(n log n + n log D), where D is the spread of the positions. Each check is a linear scan with a binary search for the jump.
O(n^2) trap: writing the check so that every flower is tried as a sprinkler centre and then all flowers are scanned again. Each check then costs n squared, and the binary search multiplies that by about 30.
Problem C: the shortest way out of a grid
A grid has R rows and C columns, with 1 <= R, C <= 1000. Each cell is one of these characters: . for an open cell, # for a wall, S for the start and E for the exit. There is exactly one S and one E. A move goes one cell up, down, left or right, into an open cell or into E. Print the smallest number of moves from S to E, or -1 if there is no path.
Input: the first line holds R and C. Then R lines each hold one row.
Sample input:
4 5
S..#.
.#...
.#.#.
...#ESample output:
7Show the answer
Run a breadth-first search from S. The first time the search reaches a cell, the step count is the shortest. Store the step count in a table and do not visit a cell twice.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int R, C;
cin >> R >> C;
vector<string> g(R);
for (auto &row : g) cin >> row;
int sr = -1, sc = -1, er = -1, ec = -1;
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++) {
if (g[r][c] == 'S') sr = r, sc = c;
if (g[r][c] == 'E') er = r, ec = c;
}
vector<vector<int>> dist(R, vector<int>(C, -1));
queue<pair<int, int>> q;
dist[sr][sc] = 0;
q.push({sr, sc});
const int dr[] = {1, -1, 0, 0};
const int dc[] = {0, 0, 1, -1};
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
if (g[nr][nc] == '#' || dist[nr][nc] != -1) continue;
dist[nr][nc] = dist[r][c] + 1;
q.push({nr, nc});
}
}
cout << dist[er][ec] << "\n";
}The sample path is (0,0), (0,1), (0,2), (1,2), (1,3), (1,4), (2,4), (3,4), which is 7 moves. The output is 7. For the second sample grid, S is walled in and the program prints -1. That grid is 3 4, rows S#.., ##.E and ..... I checked the program against a brute force on 500 random grids of up to 5 by 5 cells. The brute force repeats a relaxation step over the whole grid until no distance changes. All agreed.
Intended complexity: O(RC), because each cell enters the queue once.
O(n^2) trap: running a fresh search from every cell to check whether E is reachable from it. With a 1000 by 1000 grid that is 10^6 searches of up to 10^6 cells each. One search from S is enough.
Problem D: the cheapest hop
You start on cell 1 and you must reach cell n. From cell i you may move to cell i + 1, i + 2 or i + 3, as long as the target exists. Landing on cell j costs c_j. Starting on cell 1 is free, so c_1 is never paid. Print the smallest total cost of a route from cell 1 to cell n.
Limits: 1 <= n <= 200000, and each cost is between 0 and 10^9.
Input: the first line holds n. The second line holds c_1 to c_n.
Sample input:
5
9 1 4 9 2Sample output:
3Show the answer
The state is the cheapest cost to reach cell j, written dp[j]. Cell 1 has cost 0. For every other cell, the cheapest way to arrive is from one of the three cells before it, so dp[j] = c_j + min(dp[j-1], dp[j-2], dp[j-3]), using only cells that exist.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> c(n + 1, 0);
for (int i = 1; i <= n; i++) cin >> c[i];
const long long INF = LLONG_MAX / 4;
vector<long long> dp(n + 1, INF);
dp[1] = 0;
for (int j = 2; j <= n; j++) {
long long best = INF;
for (int d = 1; d <= 3; d++)
if (j - d >= 1) best = min(best, dp[j - d]);
dp[j] = best + c[j];
}
cout << dp[n] << "\n";
}For the sample: dp[2] = 1, dp[3] = min(1, 0) + 4 = 4, dp[4] = min(4, 1, 0) + 9 = 9, and dp[5] = min(9, 4, 1) + 2 = 3. The output is 3. I checked the program against a brute force on 500 random inputs with n up to 8. The brute force is a memoised recursion that computes the cheapest route from each cell to cell n, a top-down version of the same idea, written separately. All agreed.
Intended complexity: O(n), because each cell looks at three earlier cells.
O(n^2) trap: looping over every earlier cell i < j for each j. The sample passes. With n equal to 200000 the loop does about 2 * 10^10 steps. The window of three is the whole point of the problem.
Problem E: regions of one letter
A grid has R rows and C columns, with 1 <= R, C <= 1000. Each cell holds a lowercase letter. A region is a set of cells that all hold the same letter and are connected through shared sides (up, down, left or right). Print the number of regions and the number of cells in the largest one, separated by a space.
Input: the first line holds R and C. Then R lines each hold one row.
Sample input:
3 4
aabb
abcb
ccbbSample output:
5 5Show the answer
Scan the grid. When you meet a cell that is not yet marked, start a flood fill from it. The fill marks each cell once, so the cost is one visit per cell. Use an explicit stack, not recursion, because a recursive fill on a 1000 by 1000 grid can go a million calls deep.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int R, C;
cin >> R >> C;
vector<string> g(R);
for (auto &row : g) cin >> row;
vector<vector<char>> seen(R, vector<char>(C, 0));
long long regions = 0, biggest = 0;
const int dr[] = {1, -1, 0, 0};
const int dc[] = {0, 0, 1, -1};
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++) {
if (seen[r][c]) continue;
regions++;
long long size = 0;
vector<pair<int, int>> stack_;
stack_.push_back({r, c});
seen[r][c] = 1;
while (!stack_.empty()) {
auto [a, b] = stack_.back();
stack_.pop_back();
size++;
for (int d = 0; d < 4; d++) {
int na = a + dr[d], nb = b + dc[d];
if (na < 0 || na >= R || nb < 0 || nb >= C) continue;
if (seen[na][nb] || g[na][nb] != g[a][b]) continue;
seen[na][nb] = 1;
stack_.push_back({na, nb});
}
}
biggest = max(biggest, size);
}
cout << regions << " " << biggest << "\n";
}The sample has five regions: three a cells, one b cell in the second row, a region of five b cells on the right, one c cell, and two c cells at the bottom left. The largest has five cells. The output is 5 5. I checked the program against a brute force on 500 random grids of up to 5 by 5 cells, with letters a to c. The brute force joins equal neighbours with a union-find structure and counts the roots. All agreed.
Intended complexity: O(RC).
O(n^2) trap: allocating or clearing the seen table inside the outer loop. Each of the up to 10^6 cells then pays up to 10^6 steps for the clear, which is 10^12 steps in total.
Common mistakes
Testing only the sample. A sample has few cases, so a wrong comparison can pass it. A stress test with 300 random inputs covers many more boundary cases.
Trusting the binary search without checking the monotone claim. Before you write lo and hi, state the question "is x enough?" and check that a yes stays yes for every larger x. If it does not, binary search gives a wrong answer with no error.
Off-by-one in binary search. Use mid = (lo + hi + 1) / 2 when the loop keeps the last yes, and hi = mid - 1 when the loop moves down. Mixing the two makes the loop run forever or skip the answer.
Recursion on a large grid. A recursive flood fill on a 1000 by 1000 grid can run out of stack. The fault shows as a runtime error on large tests and not on small ones. Use an explicit stack or queue.
Using a DFS for shortest paths. A DFS can reach E by a long route first and mark cells as visited, so the step counts it stores are not the shortest. Use BFS when every move costs the same.
Forgetting the 64-bit type. Pair counts and sums can exceed 2^31. Use long long for them.
Checklist
- Set the budget per problem and the skip line before you start.
- Write the state and the transition of a DP in one line before you code it.
- For a binary search, write the yes-or-no question and check that it is monotone.
- Write a generator, a brute force and a comparison, and run 300 or more random small inputs.
- Include the boundary values: equal sums, one element, empty-looking inputs and walls.
- Compile with
g++ -std=c++17 -O2, run the sample, then run the stress test. - Look for the O(n^2) loop before you submit, and count the steps for the largest input.
Summary
Round 2 is about time and checks. A fixed budget and a skip rule stop one problem from taking the round. A stress test against a brute force finds boundary bugs that the sample cannot show. The five problems use two pointers, binary search on the answer, BFS, dynamic programming and flood fill, and each one has a simple loop that looks correct and is too slow at the largest limits.