Round 1: easy mix

Why this matters when you build with AI

When you build with AI tools, most of the work is deciding what to ask for, in what order, and how to check the answer. A contest round has the same shape in a short time. You get several tasks at once, a clock, and no way to know which task is quick until you read it. An AI model will write code for whichever task you paste first. It will not tell you that a different task was worth more points for the same minutes.

This lesson trains three habits that carry over to AI-assisted work. The first is reading everything before you start. The second is keeping a log of what happened, so you learn from the round and not only from the score. The third is comparing your result with a reference, and writing down the first point where your reasoning went wrong.

Words used in this lesson

A round is one timed set of problems. Here it has four problems and a 75-minute timer.

A statement is the text of a problem: the story, the input format, the output format and the limits.

A sample is a small example input with its expected output. The statement gives it. The judge also runs it.

A limit is the largest allowed size of the input, for example the largest n. Limits decide which algorithm you may use.

A solve order is the sequence in which you plan to attack the problems.

A simulation is a problem where the statement describes a process step by step, and the task is to run that process exactly as written.

A prefix sum is an array where entry i holds the sum of the first i values. It lets you get the sum of any range in one subtraction.

A greedy method makes the choice that looks best at each step and never goes back. It is correct only when you can show that the local choice never hurts the final answer.

Accepted means the judge ran your program on all tests and every output matched. Wrong answer (WA) means the program ran but printed something else. The site judge is described in the lesson on the site judge, in the first module of this track. It runs your code on every test, shows you two of them in full, and hides the rest.

The idea: a round is a set of decisions

A round is not four separate exercises. It is one exercise with four decisions inside it.

Order. Which problem do you start with, and which one do you leave for last?
Stopping. When do you give up on a problem for now?
Submitting. When is your code ready to send to the judge?
Recording. What do you write down so that the next round is better?

Most people spend all their effort on the third decision and none on the first. A good order is worth more than a fast typing speed, because an easy problem solved in ten minutes is worth the same points as one solved in forty, and the order decides which points you reach before the clock stops.

The round rules for this lesson

Use a real timer. A phone timer is enough. Set it to 75 minutes and do not stop it for a drink or a check of messages.

During the 75 minutes you may use your own machine, a compiler, a text editor and the sample inputs. You may not ask an AI tool, a person or a search engine for a solution, and you may not look at the editorial. This is the honest version of a contest. A round you pass with outside help tells you nothing about your own skill, and it leaves you with a false score.

The round has four problems: A, B, C and D. Each has a sample and hidden tests. Submit each one to the site judge when you think it is ready. Write the submission time in your log, including the wrong ones.

After the timer ends, open the editorial for each problem and compare. The review method is in the last section of the technique part.

Technique 1: read every statement in the first ten minutes

Most people read problem A, start coding, and find out only at minute 40 that problem C was easier. Read all statements first.

For each problem, write down four things in a table:

the one-word tag (simulation, sorting, prefix sums, math, greedy),
the largest n in the limits,
the first idea that came to you, in a few words,
an estimate of the minutes it will take: 10, 20 or 30.

Here is a filled table for a made-up round with three problems. You will not see these problems in the round. The point is the format.

problem  tag            largest n   first idea                       estimate
P         sorting       200000      sort, then compare neighbours    10 min
Q         simulation    200000      walk the steps, keep a counter   15 min
R         greedy        1000000     pick the biggest item each time  20 min

Then order the problems by the estimate, but break ties by the number of points. Problem Q is quick but may have a trap in its statement. Problem P is also quick. So P goes first, then Q, then R.

Do not spend more than 10 minutes on this scan. If you cannot name a tag, the problem is harder than it looks, and that is a reason to leave it for later.

Technique 2: start from a fixed template

Write the same few lines at the top of each program. The point is not speed of typing. The point is that reading input correctly is the first place a contest program fails.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    // read the input, solve, print
    return 0;
}

The first line includes the standard library. The second line turns off the link between C++ streams and the C input functions, which makes cin faster. The third line stops cin from flushing cout before each read. The judge compiles with g++ -std=c++17 -O2, so this file must compile with those flags. You can check that now:

g++ -std=c++17 -O2 -o template template.cpp && ./template < /dev/null; echo "exit $?"

The template prints nothing and exits with code 0, so the output on a real machine is:

exit 0

Worked example: the longest run of equal values

Here is a small problem to show the full method. It is not one of the round problems.

Statement. The first line has n, the number of values, with 1 <= n <= 200000. The second line has n integers, each between 1 and 10^9. Print the length of the longest block of neighbouring equal values. A block is a run of consecutive positions that all hold the same value.

Sample input:

8
1 1 2 2 2 1 1 1

Sample output:

Both 2 2 2 and 1 1 1 have length 3, so the answer is 3.

The idea. Walk the array once. Keep the length of the run that ends at the current position. If the current value equals the previous one, the run grows by one. Otherwise a new run starts with length 1. Keep the largest run seen so far.

The program.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;
 
    int best = 0, cur = 0;
    for (int i = 0; i < n; i++) {
        if (i > 0 && a[i] == a[i - 1]) cur++;
        else cur = 1;
        best = max(best, cur);
    }
    cout << best << "\n";
}

Compile and run it on the sample:

g++ -std=c++17 -O2 -o worked_run worked_run.cpp && printf '8\n1 1 2 2 2 1 1 1\n' | ./worked_run

The output on the machine this lesson was checked on is:

The output is the same on any machine, because the program does not depend on the platform.

I checked this program against a brute force on 500 random small inputs. The brute force is a Python script that splits each list into runs with itertools.groupby. The two programs agreed on all 500 cases.

Trace. Here is the value of cur and best after each position of the sample:

position  value  cur  best
1         1      1    1
2         1      2    2
3         2      1    2
4         2      2    2
5         2      3    3
6         1      1    3
7         1      2    3
8         1      3    3

Complexity. The loop reads each value once and does constant work per value, so the time is O(n). The array uses O(n) memory. For n equal to 200000 this is far below the judge's limits.

Pitfalls. Starting cur at 0 gives the right answer here, but writing cur = 0 at the start of the loop and then cur++ in every branch is a common slip. Read the position i - 1 only after you have checked i > 0, or the first step reads memory before the array.

The round: four problems

Set the timer now. Solve the problems in the order you chose. Each problem has a statement, a sample input with its output and a note on the limits. The editorial sits under the line Show the answer after each problem. Open it only when the timer has ended.

Problem A: tram load

A tram has capacity C. It starts empty and visits n stops in order. At stop i, first a_i passengers get off. Then b_i people try to get on. Anyone who does not fit is refused and does not board.

Print two numbers: the number of people on the tram after the last stop, and the total number of people refused over all stops.

The guarantee is that a_i is never more than the number of people on the tram at stop i. Limits: 1 <= n <= 200000, 1 <= C <= 1000000000, 0 <= a_i and b_i at most 10^9.

Input: the first line holds n and C. Then n lines follow, each with a_i and b_i.

Sample input:

Sample output:

5 3

Show the answer

The state is one number: how many people are on the tram. At each stop, subtract the people who get off. Then compute the free seats. Take min(b, free) people, and count the rest as refused.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    long long cap;
    cin >> n >> cap;
    long long onboard = 0, refused = 0;
    for (int i = 0; i < n; i++) {
        long long leave, board;
        cin >> leave >> board;
        onboard -= leave;
        long long room = cap - onboard;
        long long take = min(board, room);
        onboard += take;
        refused += board - take;
    }
    cout << onboard << " " << refused << "\n";
}

The sample output is 5 3, as the statement says. The program is O(n) in time and O(1) in extra memory. It uses long long for the refused total because the sum can reach 2 * 10^14 when n and b_i are both large.

Common trap: letting people board before the passengers get off. The sample gives the right answer for that wrong order too, so the sample does not catch it. A two-stop case does. With input 2 1 followed by 0 1 and 1 1, the correct output is 1 0: the first person boards, then the second person gets off at stop 2 and a new person boards. The wrong order prints 0 1. Always check one case by hand where a stop has both leaving and boarding.

Problem B: closest scores

You are given n integers, the scores of n contestants, in no particular order. Scores may repeat. Print the smallest value of |x - y| over two different contestants, where x and y are their scores.

Limits: 2 <= n <= 200000, each score between 0 and 10^9.

Input: the first line holds n. The second line holds the n scores.

Sample input:

5
9 3 14 7 4

Sample output:

Show the answer

Sort the scores. The two closest values are next to each other in sorted order, so one pass over neighbouring pairs finds the minimum difference.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;
    sort(a.begin(), a.end());
    long long best = LLONG_MAX;
    for (int i = 1; i < n; i++) best = min(best, a[i] - a[i - 1]);
    cout << best << "\n";
}

The sorted sample is 3 4 7 9 14, and the neighbour gaps are 1, 3, 2 and 5. The smallest is 1. The cost is O(n log n) for the sort. Checking all pairs would take about 2 * 10^10 comparisons for n equal to 200000, which is far too slow for a 5-second limit.

Common trap: forgetting the sort. On the sample, the same loop without sort prints -7, because the neighbour pair 7 and 14 gives 7 - 14 = -7, which is the smallest value. After the sort, every neighbour difference is zero or positive.

Problem C: noise log

A sensor records the noise level in each of n minutes. Each level is an integer from 0 to 100. Then q questions follow. Each question gives two minutes l and r, with 1 <= l <= r <= n. For each question print the sum of the noise levels from minute l to minute r, both included.

Limits: 1 <= n, q <= 200000.

Input: the first line holds n and q. The second line holds the n levels. Then q lines follow, each with l and r.

Sample input:

6 3
3 0 5 2 7 1
1 3
2 5
6 6

Sample output:

8
14
1

Show the answer

Build a prefix sum array p, where p[i] is the sum of the first i levels, with p[0] = 0. The sum from l to r is p[r] - p[l - 1].

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, q;
    cin >> n >> q;
    vector<long long> p(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        long long v;
        cin >> v;
        p[i] = p[i - 1] + v;
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << p[r] - p[l - 1] << "\n";
    }
}

The output on the sample is 8, 14 and 1. The building step is O(n), and each question takes O(1). Adding the values again for each question would take up to 4 * 10^10 additions in the worst case.

Common trap: the off-by-one error. Writing p[r] - p[l] drops the value at minute l. On the sample the program then prints 5, 14 and 0 instead of 8, 14 and 1. The first question shows the cause: p[3] - p[1] is 8 - 3 = 5. Check every formula with the smallest case l = r.

Problem D: shop change

A shop gives change with coins of 50, 25, 10, 5, 2 and 1 cents. You have to give exactly A cents, where 0 <= A <= 10^9. You may use any number of each coin. Print the smallest number of coins that adds up to A.

Input: one integer A.

Sample input:

Sample output:

Show the answer

Use the largest coin as many times as it fits, then the next coin, and so on. This is a greedy method. It gives the right answer for this coin set, as the check below shows.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    long long amount;
    cin >> amount;
    const long long coins[] = {50, 25, 10, 5, 2, 1};
    long long count = 0;
    for (long long c : coins) {
        count += amount / c;
        amount %= c;
    }
    cout << count << "\n";
}

For 68 the steps are: one 50 leaves 18, no 25, one 10 leaves 8, one 5 leaves 3, one 2 leaves 1, one 1 leaves 0. That is 5 coins.

Honest scope: the greedy is correct for this coin set. I checked it against an exact dynamic programming count for every amount from 1 to 100000, and all agreed. I have not written a proof that covers every amount up to 10^9. The check is evidence, not a proof. For a contest, that is enough to submit, but do not assume that greedy works for an arbitrary coin set.

Counterexample for a different set: the coins 1, 3 and 4 with amount 6. The greedy takes 4, then 1, then 1, which is 3 coins. The best is 3 and 3, which is 2 coins. The program above prints 3 when the coin list is changed to {4, 3, 1}, and the correct answer is 2. So the same code is wrong for that set. Check the coin set before you trust greedy.

After the round: the review habit

The review is where most of the learning happens. Do it on the same day. A review done three days later is mostly a reading of the editorial, and you lose what you could have learned from your own wrong attempts.

For each problem, write a short log entry with five parts:

problem:
accepted (yes or no), and the minute of the first accepted submission:
wrong submissions before it:
first wrong idea (one sentence, the moment I went wrong):
missed edge cases (list them, each with a small input):

The first wrong idea is the earliest decision that was not correct. It is not the last bug you fixed. For problem A it might be "I let people board before anyone gets off." For problem C it might be "I used the formula with l instead of l - 1."

The missed edge cases are the inputs your program would have failed on. A good edge case is small enough that you can run it by hand, and it matches the way your program fails. Write it as an input, not as a sentence.

To check your own sense of which edge cases matter, use a small brute force program. A brute force is a slow program that is easy to trust. For problem B, the brute force checks every pair. Compare its output with your fast solution on random small inputs. The stress test method is in the round 2 lesson.

When you use an AI tool in the review, give it the statement, your code, the failing input and the editorial, and ask for a focused answer. Here is a prompt that works. Fill in the three places marked with angle brackets.

Here is the statement of a contest problem, my program and the editorial.
Do not write new code. Tell me the first decision in my program that does not
match the editorial, and quote the single line of my code where it happens.
Then give one input with at most five numbers where my program and the
editorial's idea would give different answers, and say what each would print.
 
Statement:
<paste the statement>
 
My program:
<paste the code>
 
Editorial idea:
<paste the one-paragraph idea, not the full editorial code>

A good answer names one line of code, one decision and one small input. Check the answer before you believe it: run your program and a brute force on that input. If the tool gives you a long rewrite, or names a line that does not exist, it is guessing. Ask again with the line numbers marked, or discard the answer.

Two errors to watch for. The tool may call the code "almost right" and propose a different algorithm, which hides the real bug. It may also state a counterexample without running it. Always run the input.

Common mistakes

Starting with the first statement. The first problem is not always the best place to start. Scan all four first.

Reading the sample and assuming the code is right. The sample is one input. In problem A, the sample passes with the wrong boarding order. Always write one small case by hand.

Using int for big sums. In problem A, refused can reach 2 * 10^14. An int overflows, and signed overflow is undefined behaviour in C++, so the printed value is wrong in a way that may look plausible. Use long long for every sum over many values.

Submitting without a log. A round you do not log gives one number, the score. The log gives the cause of each lost point.

Changing the editorial code without comparing. When you read the editorial, do not copy its code into your file. Find the line where your idea differs from it, fix only that line and run your program on the small input again.

Checklist

Read all statements and fill the scan table in ten minutes or less.
Choose the order by estimated minutes and by points.
Compile with g++ -std=c++17 -O2 before you submit.
Check the sample, then one small case you worked out by hand.
Use long long for sums and for products of values.
Log each submission, with its time and verdict.
After the timer, compare with the editorial and write the first wrong idea.
List the edge cases you missed, each as a small input.

Summary

A round is four decisions: order, stopping, submitting and recording. The fastest contest result comes from reading every statement first, choosing an order, and keeping a log that says where minutes were lost. The four problems in this round cover simulation, sorting, prefix sums and greedy, and each one has a trap that a sample input can hide. The review asks for one first wrong idea and a few small inputs, and an AI tool can help with that only if you run what it suggests.