Final mixed round, review and a training log

Why this matters when you build with AI

When you build with AI tools, the output looks finished long before it is checked. A generated function can read cleanly, pass the first example and still fail on the largest input, or on a case with a zero or a negative number. The same thing happens in a contest. A solution that looks right is not evidence that it is right, and the only way to learn your own pattern of mistakes is to keep a record of them.

This lesson closes the track with a timed mixed round, a full review and a training log. The log is a small table that you fill in after every round. Over several rounds it shows what you are actually bad at, and that is more useful than a feeling of being bad at everything.

Keep the rule of this lesson in mind from the start. A timed round is a measurement, so no outside help is allowed during it. That means no AI assistant, no search for the answer, no reading of an editorial and no asking a friend. The moment you use any of these, the round tells you nothing about your own skill.

The idea: a round is a measurement

Here are the words used in this lesson, defined once.

A verdict is the judge's answer to one submission. AC means accepted. WA means wrong answer, which is a program that ran but printed a wrong result on at least one test. TLE means time limit exceeded, which is a correct program that ran too slowly. RE means runtime error, which is a crash.
An editorial is the written solution that a contest or a site publishes after the round. Reading it during the round removes the point of the round.
Upsolving means solving a problem you missed, after the timed round ends. It is useful practice, but its result is not a timed result, so log it separately.

A round gives you one row per problem attempt. The row records the problem, the topic, the verdict, the minutes you spent, and the error category if the verdict was not AC. The categories in this lesson are:

WA: the answer was wrong on some test. Usually the logic or a case was missed.
TLE: the answer was right but too slow. Usually the algorithm was too heavy for the limits.
overflow: a number was too big for its type and wrapped around or became negative. Usually a product or a sum was stored in an int.
misread: the program solved a different problem from the one asked. Usually an inclusive bound was treated as exclusive, rows and columns were swapped, or the answer was asked modulo a number and was not printed that way.

These four categories cover most of the mistakes in the training log below. If you cannot place a mistake in one of them, add a fifth category and name it, so the log stays honest.

The round

The round has six original problems. You have 120 minutes. Write the plan in the first 10 minutes, then start. The problems are below with statements, limits and samples. Use the sample inputs to check your reading of each statement before you code.

F1. Balanced teams. You have n players with skill values a_i, and a number d. A team is two players whose skills differ by at most d. A player can be in at most one team. Output the largest number of teams. Limits: 1 <= n <= 200000, 0 <= d, 0 <= a_i <= 1000000000. Sample input: 6 2 on the first line and 1 9 4 8 3 5 on the second. Sample output: 3.

F2. Steady lamps. There are n lamps in a row, with brightness values b_i, and a number K. Count the contiguous segments of lamps whose largest and smallest brightness differ by at most K. A single lamp counts as a segment. Limits: 1 <= n <= 200000, 0 <= K, and 0 <= b_i <= 1000000000. Sample input: 5 2 and 1 3 2 6 4. Sample output: 9.

F3. Walls with breaks. You are given a grid with R rows and C columns. Each cell is . (open), # (wall), S (start) or E (exit). You move up, down, left or right, one cell per step. You may walk into up to K wall cells over the whole route, each one costing one of your K breaks. Output the fewest steps from S to E, or -1 if it cannot be done. Limits: 1 <= R, C <= 50 and 0 <= K <= 3. Sample input: 3 4 1, then the three rows S.#., ##.# and ...E. Sample output: 5.

F4. Stair steps. A staircase is climbed with steps of size 1, 2 or 5. Two climbs are different if the sequence of steps differs, even if the total is the same. Count the climbs that reach exactly n steps, modulo 1000000007. Limits: 0 <= n <= 100000. Sample input: 7. Sample output: 26.

F5. Square pairs. Count the pairs of integers a and b with 1 <= a <= b <= N and where a * b is a perfect square. Limits: 1 <= N <= 1000000. Sample input: 10. Sample output: 14.

F6. Pattern hits. You get two strings s and t. Count the positions i in s where t starts. Hits may overlap. Limits: 1 <= |s|, |t| <= 200000, lowercase letters only. Sample input: abababa and then aba. Sample output: 3.

The review is part of the round, not something you do later. Do it the same day, while the timer is fresh in your memory.

Worked review: F3 walls with breaks

F3 is the worked example. Read the statement, then write your own solution before you read this section.

The first idea most people try is a plain breadth-first search on cells, with walls treated as impassable. Breadth-first search explores cells in order of distance, so the first time it reaches the exit is the shortest route. That is correct for paths without breaks, and it is the first wrong idea here. It ignores the break budget entirely.

Run that idea on the sample by setting the budget to zero. This is what the solution below prints with K = 0 on the same grid.

3 4 0
S.#.
##.#
...E

Output: -1

With no breaks, the exit is unreachable, so -1 is right for this input. The real sample has K = 1, and the answer 5 needs one break. The first wrong idea would print -1 on the real sample, which is how you can tell it is missing the break budget.

The technique: BFS over states

A state is more than a cell. Here the state is the pair (cell, breaks used so far). Two visits to the same cell with different break counts are different states, because the one with more breaks left can do things the other cannot.

Breadth-first search works on states the same way it works on cells, as long as every move costs one step. Each state is visited at most once, and states are explored in order of their step count. The first time the exit is popped from the queue, with any break count, that is the fewest steps.

The number of states is R * C * (K + 1), which is at most 2500 * 4 = 10000 here. That is far below any limit.

Here is the C++17 solution.

#include <bits/stdc++.h>
using namespace std;
// F3: grid with walls. You may break up to K walls. Output the fewest steps from S to E, or -1.
// State = (row, column, walls broken so far). Plain BFS over these states.
int main() {
    int R, C, K;
    scanf("%d %d %d", &R, &C, &K);
    vector<string> g(R);
    char buf[256];
    for (int i = 0; i < R; i++) {
        scanf("%s", buf);
        g[i] = buf;
    }
    int sr = -1, sc = -1, er = -1, ec = -1;
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++) {
            if (g[i][j] == 'S') sr = i, sc = j;
            if (g[i][j] == 'E') er = i, ec = j;
        }
    auto id = [&](int r, int c, int k) { return (r * C + c) * (K + 1) + k; };
    vector<int> dist((size_t)R * C * (K + 1), -1);
    queue<int> q;
    dist[id(sr, sc, 0)] = 0;
    q.push(id(sr, sc, 0));
    int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
    while (!q.empty()) {
        int s = q.front();
        q.pop();
        int k = s % (K + 1);
        int cell = s / (K + 1);
        int r = cell / C, c = cell % C;
        if (r == er && c == ec) {
            printf("%d\n", dist[s]);
            return 0;
        }
        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;
            int nk = k;
            if (g[nr][nc] == '#') {
                if (k == K) continue;   // no break left
                nk = k + 1;
            }
            int t = id(nr, nc, nk);
            if (dist[t] == -1) {
                dist[t] = dist[s] + 1;
                q.push(t);
            }
        }
    }
    printf("-1\n");
    return 0;
}

Compile and run it on the sample:

$ g++ -O2 -std=c++17 -o f3 f3.cpp
$ ./f3 < f3_sample.txt
5

The sample has two routes of five steps, and each uses one break. One goes right to the top row's second cell, down through the wall below it, down once more, then right to the exit. The other goes down through the wall at the start's lower neighbour, down once more, then right along the bottom row.

Two more runs check the edges of the problem. These are the cases the review should look for.

$ printf '1 3 1\nS#E\n' | ./f3
2
$ printf '1 3 0\nS#E\n' | ./f3
-1

With one break, S#E needs two steps: one into the wall, one out to the exit. With zero breaks it cannot be done.

Complexity

Each state is pushed at most once, and each state looks at four neighbours. The total time is O(R * C * K), and the memory for the distance array is the same. With the limits, this is at most about 10000 states, so it is much faster than the limit.

I tested this solution against a brute force that repeats relaxation over all states until nothing changes, on 400 random grids with at most 5 rows, 5 columns and 2 breaks. Every answer matched. The brute force uses a different algorithm, so it does not share the same bug. This is a small test, and it shows the logic is right on small grids.

Common pitfalls

Treating a break as free, or as a separate cost. Each break uses one of the K budget and costs one step, so it is one step with a budget check.
Forgetting that the exit can be a state reached with fewer breaks. The solution takes the first popped exit state, which is correct because BFS pops in step order.
Marking a cell visited without its break count. A cell visited with zero breaks does not block a later visit with one break, so the visited array must include the break count.
Reading the grid with scanf("%s") into a fixed buffer that is too small. The limit here is 50 columns, which fits the 256-byte buffer.

Worked training log

The training log is a table you fill in after every round. Here is the summary script. It reads an embedded log, groups the rows by topic, and prints accepted counts, accept rates, median minutes for accepted problems and error categories. Save it and run it.

Python · editable

# Training log summary. Each row: round, topic, verdict, minutes spent, error category ("-" if accepted).
from collections import defaultdict
import statistics

log = [
    ("R1", "greedy", "AC", 18, "-"),
    ("R1", "prefix sums", "AC", 9, "-"),
    ("R1", "sorting", "WA", 25, "misread"),
    ("R1", "sorting", "AC", 31, "-"),
    ("R2", "two pointers", "AC", 22, "-"),
    ("R2", "binary search", "TLE", 40, "TLE"),
    ("R2", "binary search", "WA", 45, "WA"),
    ("R2", "dp", "WA", 60, "overflow"),
    ("R3", "dp", "AC", 52, "-"),
    ("R3", "graphs", "AC", 38, "-"),
    ("R3", "graphs", "WA", 70, "WA"),
    ("R3", "graphs", "AC", 95, "-"),
]

by_topic = defaultdict(lambda: {"attempts": 0, "ac": 0, "times": [], "errors": defaultdict(int)})
for rnd, topic, verdict, mins, err in log:
    t = by_topic[topic]
    t["attempts"] += 1
    if verdict == "AC":
        t["ac"] += 1
        t["times"].append(mins)
    else:
        t["errors"][err] += 1

print(f"{'topic':<15}{'tries':>6}{'AC':>4}{'rate':>7}{'median_min':>12}  errors")
for topic, t in sorted(by_topic.items(), key=lambda kv: kv[1]["ac"] / kv[1]["attempts"]):
    rate = t["ac"] / t["attempts"]
    med = statistics.median(t["times"]) if t["times"] else float("nan")
    errs = ", ".join(f"{k}={v}" for k, v in sorted(t["errors"].items())) or "none"
    print(f"{topic:<15}{t['attempts']:>6}{t['ac']:>4}{rate:>7.2f}{med:>12.1f}  {errs}")

all_errors = defaultdict(int)
for _, _, verdict, _, err in log:
    if verdict != "AC":
        all_errors[err] += 1
print("error categories:", dict(sorted(all_errors.items())))
weak = [topic for topic, t in by_topic.items() if t["ac"] / t["attempts"] < 0.5]
print("weak topics (accept rate below 0.5):", sorted(weak))

Output:

topic           tries  AC   rate  median_min  errors
binary search       2   0   0.00         nan  TLE=1, WA=1
sorting             2   1   0.50        31.0  misread=1
dp                  2   1   0.50        52.0  overflow=1
graphs              3   2   0.67        66.5  WA=1
greedy              1   1   1.00        18.0  none
prefix sums         1   1   1.00         9.0  none
two pointers        1   1   1.00        22.0  none
error categories: {'TLE': 1, 'WA': 2, 'misread': 1, 'overflow': 1}
weak topics (accept rate below 0.5): ['binary search']

The sample log is invented for this lesson, so its numbers mean nothing about you. The point is the shape of the output. The binary search row has two tries and no accepted problem, with one TLE and one WA, so the script flags it as a weak topic. The graphs row shows that a WA can be followed by an AC in the same topic, which is normal.

Some notes on reading the output.

The median is more honest than the average for minutes, because one long problem can pull the average far up. A median of 31 minutes means half the accepted problems took 31 minutes or less.
A topic with only one or two tries is not a verdict on that topic. Keep the rule, weak means below 0.5 accept rate, and treat it as a hint about where to look next round.
The error categories tell you what to practise. Two WA and one TLE in binary search point to different fixes: WA means the check or the boundary is wrong, TLE means the check is too slow or the search is over the wrong range.

For your own log, keep the same columns in a plain text or CSV file, one row per attempt. Do not edit old rows. If you change your mind about a category, add a note on the row rather than rewriting history.

Reviewing after the timer

Do the review in this order, for each problem, on the day of the round.

Write down the verdict and the minutes you spent.
Find the first idea you had that was wrong. Write it in one line, as the wrong idea. For F3 that is the plain BFS that ignores the break budget.
List the edge cases you missed. For F3, a grid where the start is next to the exit, and a grid with zero breaks, are both cases to check.
Read the editorial or the solution only after steps 1 to 3. Compare your idea with it. Note the step where your reasoning first diverged.
Write one checklist item that would have caught the mistake before submission.

Step 2 is the one most people skip, and it is the most useful. Your first wrong idea is the pattern you will repeat. A log that records the wrong idea for each problem will show you the same pattern across rounds.

Common mistakes

Reading the editorial during the round. This removes the measurement, and the log then records a skill you did not use.
Writing a brute force that shares the same bug as the solution. A brute force that uses the same wrong assumption cannot catch the bug. Use a different method, for example repeated relaxation instead of BFS, as the F3 test does.
Reading a limit as a suggestion. A solution for N up to 10^6 that loops over all pairs does about 5 * 10^11 steps, and the judge returns TLE. Compute the worst case from the limits before you code.
Overflow from one multiplication. In F5, a * b can reach 10^12, which does not fit in a 32-bit int. If it is stored in an int, it wraps around and the answer is silently wrong. You will typically see a WA on a large case while the small cases pass.
Modulo and negatives. In C++ the % operator can return a negative number for a negative input, so a result like (x - y) % MOD may need adding MOD before it is printed. F4 avoids this because all its values are positive.
Treating a log as a score. A log exists to show patterns. Writing down a good row and skipping a bad one makes it useless.
Using an AI assistant during the timed round, and then recording the result as your own. The result is not a measurement of your skill, and the log will be wrong from that day on.

AI tools: what they get wrong and how to catch it

An AI assistant can write a plausible solution, a plausible brute force and plausible tests in one reply. None of those three is evidence on its own. The useful habits are these.

Ask for the brute force first and run it on the sample before you trust the solution. A brute force that disagrees with the sample is a sign that the statement was misread.
Check the complexity claim by counting operations at the largest limit. Models often state a complexity that is wrong for the loop structure they wrote.
Generate random small tests yourself, using the statement's limits, rather than accepting tests the assistant writes. A generator written with the same misreading produces tests that agree with the wrong solution.
Compare with a second method, not the same method written twice. The F3 check uses a different algorithm from the solution for this reason.

These habits take a few minutes. They also keep the training log honest, because the verdict you record is then the verdict of your own work.

Planning the two-hour window

In a six-problem round, the plan is the first decision, and it is written before any coding. Use these steps in the first ten minutes.

Read all six statements. Mark each problem with a topic guess and a time guess.
Compute the time budget for each problem from its guess, using the same weighting as the budget table in the time-per-problem lesson. Leave 15 minutes at the end for checks.
Write the order you will attempt. Put the problem with the best expected points per minute first.
Write the abandon rule for each problem. For example: if no new idea appears for 15 minutes, switch and write one line on the wrong idea.

Partial credit is a related idea. In an olympiad-style subtask set, a solution that is correct on small limits earns points. In a plain contest like this one, a solution that is correct only on small limits earns nothing, so do not plan a round on partial credit.

Virtual contests

A virtual contest runs a past contest, or a practice set, at a time you choose, with the same timer and problem set. Public sites offer some version of this. The rules differ between sites, and they can change, so check the current rules page of the site you use before each round. This lesson does not state the rules of any particular site.

Whatever the site's rules, the honest version of a virtual round follows the same discipline as this lesson's round. During the timer, use no outside help: no AI assistant, no search for solutions, no editorial, no shared notes from other people. Record the verdicts and minutes in your log. After the timer ends, you can read editorials and upsolve, but mark those rows as upsolving in the log.

A practical plan for the next four weeks looks like this. Run one timed round each week, with the same two-hour window, and the same log. Each round, pick the weakest topic from the log and write one practice set for it. After each round, add the rows, and check whether the weak-topic list is shorter. A list that does not shrink after several rounds means the practice is not targeting the real error, so look at the error categories and change the practice.

Checklist

Write the plan in the first ten minutes. Read all statements before coding.
Check every problem's worst case against its limits before you submit.
Run the sample, then a small random test against a brute force with a different method.
After each WA, find the failing input before the next submission.
Log each attempt with the problem, topic, verdict, minutes and error category.
Write the first wrong idea for each problem after the round.
Keep the round timed with no outside help, and mark upsolving rows separately.
Review the log once a week and pick one weak topic for the next practice set.

Practice

Each practice item has an answer under the line "Show the answer".

Practice 1. Your log. Write your own log for one timed round, with at least five rows, using the columns from the worked training log. Add an error category to each non-AC row. Then count the AC rows and the rows per category. What does the count say about the topic with the most errors?

Show the answer

There is no single correct log, because it is your data. A good log has one row per attempt, with a category on each non-AC row, and the count of AC rows matches the number of AC verdicts you wrote. The topic with the most errors is the first candidate for the next practice set. Check that the category counts add up to the number of non-AC rows.

Practice 2. The grid with one break. Run the F3 solution on the grid 1 3 1 with rows S#E, and then on the same grid with K = 0. What do you expect, and what does the run print?

Show the answer

With one break, the route goes through the wall once, so the answer is 2. With zero breaks there is no route, so the answer is -1. The runs print 2 and -1.

Practice 3. Count the square pairs. Use the F5 solution to count the pairs for N = 20. Then check the number by hand, using the square-free part of each number: two numbers form a square product exactly when their square-free parts are equal.

Show the answer

The program prints 31. By hand, the square-free parts from 1 to 20 are: 1, 2, 3, 1, 5, 6, 7, 2, 1, 10, 11, 3, 13, 14, 15, 1, 17, 2, 19, 5. The class with part 1 has four numbers (1, 4, 9, 16), so it gives 10 pairs. The class with part 2 has three numbers (2, 8, 18), giving 6. The class with part 3 has two (3, 12), giving 3. The class with part 5 has two (5, 20), giving 3. The nine other numbers each form a class of one, giving one pair each, so 9. The total is 10 + 6 + 3 + 3 + 9 = 31.

Practice 4. Classify the symptom. For each symptom, name the error category: (a) the program prints the right answer on every small test and the judge says TLE on the largest test; (b) a product of two large numbers is negative in the output; (c) the program reads rows as columns and gets the right answer for a square grid only; (d) the program prints the wrong answer on a random small test that the brute force handles correctly.

Show the answer

(a) TLE, because the answer is right and the time is the only problem. (b) overflow, because a product wrapped around in a fixed-size type. (c) misread, because the statement was read differently from the input. (d) WA, because the logic is wrong on a case the small tests found.

Summary

A timed round with no outside help is a measurement, and the training log turns repeated measurements into a list of what to practise next. Plan the round in ten minutes, check each solution against a brute force that uses a different method, and record the first wrong idea for each problem.