Team contest set and penalty timeline

Why this matters when you build with AI

When you build with AI tools, one person often sits at one screen and types everything. A team with one computer has the same bottleneck. Two people typing at once make a mess, and one person reading the output while another types is slow. An AI assistant makes this worse in a quiet way. It can write a full solution in a minute, and that speed tempts you to submit before anyone checks the answer on a small case. A wrong answer then costs time and penalty, and the penalty is shared by the whole team.

Team contests are a clean model for this. You have one computer, a fixed time, a shared score, and a rule that makes every wrong submission expensive. This lesson teaches the working habits that keep a team fast: split the roles, order the work by value, check before you submit, and record what happened so the next round goes better.

Team practice here is with your own team only. Follow the rules of the contest you are simulating. In a real team contest there is one computer per team, the team works alone, and outside help during the contest is not allowed. Read the rules of the event you plan to enter, because they set the details.

The idea: one computer, three roles, one penalty

A team contest in the ICPC style has a few fixed rules, and the scoring rule is the one that shapes everything else.

The score has two numbers. The first is how many problems the team solved. The second is the penalty, which is a time. For each solved problem, the penalty is the minute of its first accepted submission, plus 20 minutes for every wrong submission made before that accepted one. Problems that are never solved add nothing. The team with more solved problems ranks higher, and the team with less penalty wins a tie.

The ICPC rules text (the official help page at submit.icpc.global/help/rules) describes this 20-minute rule. The same help text says that compile errors do not carry the 20-minute penalty. Other contests may use other penalty values, so the rules page of your event is the authority.

What the penalty counts

Two words are used throughout this lesson.

• A verdict is the judge's answer to one submission, for example AC for accepted, WA for wrong answer, TLE for time limit exceeded, RE for runtime error, or CE for compile error.
• A timeline is the list of your submissions in time order, with the problem, the minute and the verdict.

Here is a worked timeline. A team submits five times in the first 130 minutes:

• Problem C at minute 25, wrong answer.
• Problem C at minute 41, wrong answer.
• Problem C at minute 58, accepted.

That problem costs 58 + 2 * 20 = 98 penalty minutes. The two wrong answers add 40 minutes, not 40 minutes of clock. The clock still ran to minute 58.

Now the full worked example. Save this as a script and run it. The script reads an embedded timeline, applies the penalty rule and prints a scoreboard row for each problem.

The output on this timeline is:

problem  solved_at  wrong  penalty
A               12      0       12
B              130      1      150
C               58      2       98
D                -      1        0
problems solved: 3, total penalty: 260

Read the rows slowly. Problem B has one wrong answer at minute 70 and a compile error at minute 95. The compile error is ignored, so B costs 130 + 20 = 150. Problem D was attempted once and never accepted, so it adds nothing, even though the team did spend a submission on it.

The script has one line that matters most for real contests: if p in solved: continue. After the first accepted submission, later submissions to the same problem do not change the score. A team that resubmits an accepted problem to check it again does not lose penalty, but it does spend the attention of the person who should be reading the next problem.

What this means for decisions

Each wrong answer costs 20 minutes of penalty only if you later solve the problem. If you never solve it, the wrong answers cost nothing in penalty. But a guess still uses a judge attempt and the coder's attention, and it delays the check that would have caught the bug.

The practical rule is that a submission must have passed a test you ran yourself. Run the sample input. Run one small case you can check by hand. Run the brute force from the debugger role on random small inputs. Only then submit.

The three roles

The team has one computer and three people. The three roles split the work so that nobody waits for a screen they cannot use.

Reader

The reader reads every statement at the start, before anyone types. The reader does not write code.

The reader's job is to write one line per problem in a plan table: the problem letter, a guess of the topic, a guess of the time to solve, and a guess of the chance of solving it within the time. These guesses will be wrong sometimes. That is fine, as long as the team records them so it can compare with what happened.

The reader also calls the time at each checkpoint.

Coder

The coder writes the solution. The coder takes the plan from the reader, writes the main code, and is the only person typing the solution.

The coder should not look at the debugger's random tests until the solution is written. If both make the same wrong assumption, no brute force catches it, so both must read the statement carefully.

Debugger

The debugger writes the brute force. A brute force is a slow program that is easy to trust because it does the most direct thing: it tries every possibility on a small input. The debugger also writes a small random input generator, runs both programs on many small inputs, and reports the first input where they disagree.

The debugger does not type the main solution. Splitting it this way means the coder is not the only person who checks the code.

Rotating roles on one computer

When you practise alone, you play all three roles in turn, with a timer for each block. A workable block for one problem is 5 minutes as reader, 20 as coder and 10 as debugger. Write the role next to each event in the timeline.

The real benefit is that when you are the debugger, you read the coder's code as a stranger would. That habit finds the bug that the coder, who wrote the code, cannot see.

Ordering problems by expected points per minute

The reader's plan is only useful if the team uses it to choose what to read and what to type next. The simplest useful measure is expected points per minute.

For each problem, multiply the points by the chance of solving it, then divide by the minutes you expect it to take. This gives expected points per minute. A problem with a high value and a small time is cheap to try. A problem with a huge time and a low chance is expensive.

Here is the table from a team plan, and the script that ranks it. The numbers are guesses made at the start, and the team should check them after each problem.

Output:

rank  problem  points  minutes  chance  expected_points_per_minute
   1     A        500       15    0.90                       30.00
   2     C       1000       30    0.45                       15.00
   3     B       1000       45    0.60                       13.33
   4     D       1500       90    0.20                        3.33
   5     E       2000      120    0.10                        1.67

The ranking says to read A first, then C, then B. Problem E has the largest value, but it ranks last, because a 10 percent chance over 120 minutes gives little expected score per minute.

Three cautions keep this honest.

• The chance and the minutes are guesses. Update them after each problem, and write the actual minutes next to the guess.
• The ratio is a rule of thumb, not a proof. Choosing the best set of problems for a fixed time is a knapsack choice, and the ratio is a fast approximation of it.
• Solving the shortest problems first keeps each solve minute small. If you are sure you will solve every problem in the set, sorting by time is the order that keeps the sum of solve minutes low. In a real contest you will not be sure, so the ratio is the safer rule.

If the team ignores this, it often starts with the most interesting problem, which is usually the hardest, and the easy solves come late. The penalty goes up.

Debugging without stopping the coder

The debugger's job is to find the smallest input on which the coder's solution fails. The method has four steps.

1. Write the brute force first, in the simplest form that is obviously correct, even if it is slow.
2. Write a generator that makes small random inputs, with small limits so the brute force can finish.
3. Run both programs on the same inputs, and compare the outputs.
4. When they differ, reduce the failing input by hand until it is as small as you can make it, then send the coder that input.

Here is a stress test for problem B, the bus shelter problem from the worked example below. It runs the solution against a brute force on 300 random inputs. The solution file path is the one the coder compiled.

Note that this script refers to a compiled binary at a fixed path. On your machine, change BIN to the path of your own compiled solution. The output will be cases: 300, mismatches: 0 when the solution agrees with the brute force on all 300 inputs.

A stress test checks many inputs at once. Here is a deliberate bug: the coder changed one comparison from <= to <, so each shelter covers one fewer position on the right.

correct solution on sample 6 2 / 1 3 4 8 9 12:   2
changed comparison (x[i] < p + D) on the same:   3

The buggy version prints 3 where the correct answer is 2, so the sample alone already exposes it. A team that only reads the output and never runs a brute force would have to guess which comparison was changed.

Worked problem: bus shelters

This problem is the worked example. Read the statement, then try it yourself before you read the solution.

Statement. There are n houses on a straight street, at distinct integer positions x_1 to x_n, given in increasing order. You can place at most k bus shelters at integer positions. Every house walks to its nearest shelter. Output the smallest possible value of the longest walk any house must make.

Input. The first line has n and k. The second line has the n positions. Limits: 1 <= k <= n <= 200000, and 0 <= x_i <= 1000000000.

Sample input and output.

6 2
1 3 4 8 9 12

Output: 2

The answer is 2. Shelters at 2 and 10 leave no house more than 2 steps away: houses 1, 3, 4 are at most 2 from 2, and houses 8, 9, 12 are at most 2 from 10. Distance 1 is not enough, because the three houses 1, 4 and 8 cannot all be served from two positions within 1 of them.

The technique: binary search on the answer

Instead of asking directly for the best placement, ask a yes or no question. Given a distance D, can k shelters cover all houses so that each house is within D of a shelter? The answer is monotone: if D works, then any larger D also works. Monotone means the answer flips from no to yes once and stays yes. That property lets you binary search over D.

To check a given D, use a greedy sweep. Walk from left to right. At the first house that is not yet covered, place a shelter as far right as it can go while still covering that house. A shelter at x + D covers every house from x to x + 2D. Then skip all houses covered by that shelter and repeat. If the number of shelters needed is at most k, the check passes.

Why place the shelter at x + D and not earlier? Placing it further right covers more houses to the right, and the houses to the left of x are already covered by earlier shelters. Moving the shelter left would cover fewer houses to the right, and nothing is gained on the left.

Here is the C++17 solution. It uses long long for positions so that x + D cannot overflow.

#include <bits/stdc++.h>
using namespace std;
// Problem B: bus shelters. Binary search on the answer D, greedy check.
int n, k;
vector<long long> x;
 
bool ok(long long D) {
    int cnt = 0;
    int i = 0;
    while (i < n) {
        cnt++;
        if (cnt > k) return false;
        long long p = x[i] + D;   // shelter placed as far right as still covers house i
        while (i < n && x[i] <= p + D) i++;
    }
    return true;
}
 
int main() {
    scanf("%d %d", &n, &k);
    x.resize(n);
    for (auto &v : x) scanf("%lld", &v);
    long long lo = 0, hi = x[n - 1] - x[0];
    while (lo < hi) {
        long long mid = (lo + hi) / 2;
        if (ok(mid)) hi = mid;
        else lo = mid + 1;
    }
    printf("%lld\n", lo);
    return 0;
}

Compile and run on the sample:

$ g++ -O2 -std=c++17 -o b b.cpp
$ ./b < b_sample.txt
2

The upper bound hi = x[n-1] - x[0] is safe because one shelter at the first house already keeps every house within the length of the street.

Complexity

The check runs in O(n) time, because each house is passed once. The binary search runs about log2 of the street length, which is at most 30 steps for values up to 1000000000. The total time is O(n log C), where C is the largest coordinate. Memory is O(n).

I tested this solution against a brute force that tries every set of up to k integer shelter positions inside the street. The test is in the stress script above, with 300 random inputs of at most 6 houses and positions up to 12. Every answer matched. This is a small test, not a proof. The brute force only covers small inputs, so the test checks the logic, and the complexity argument covers large inputs.

Common pitfalls

• Placing the shelter at x[i] + D as an exclusive bound. The check must use <=, as in the buggy example above, which gives 3 on the sample where the answer is 2.
• Using int for positions and sums. Coordinates up to 10^9 plus D can exceed the int range. The solution above uses long long.
• Binary searching with the wrong direction. If ok(mid) is true, the answer is at most mid, so the search moves hi down. Reversing that gives a wrong answer that looks plausible.
• Forgetting that shelters must be at integer positions. Here x + D is an integer because both are integers, so no rounding is needed.

The team set

Read all five statements, and fill in the reader's plan table, before you type. The simulated time is 180 minutes.

Problem A. Multiples in ranges. You get n integers a_1 to a_n, and q queries. Each query gives l and r, and asks how many values in positions l to r are multiples of 3. Limits: 1 <= n, q <= 200000, and 0 <= a_i <= 1000000000. Input: first line n q, second line the values, then q lines with l r.

Sample input:

6 2
3 4 6 7 9 1
1 3
2 6

Sample output: 2 and 2.

Problem B. Bus shelters. The worked problem above, with the same statement and sample.

Problem C. Road repairs. There are n cities numbered 1 to n, and m roads. Each road is given as u v c built, where c is the cost of building it and built is 1 if the road already exists or 0 if it does not. Existing roads are free and always present. Output the smallest total cost of new roads that connects all cities, or -1 if that is impossible. Limits: 1 <= n, m <= 200000, and 1 <= c <= 1000000000.

Sample input:

4 4
1 2 5 0
2 3 4 0
3 4 7 0
1 4 3 1

Sample output: 9. The existing road 1 to 4 is free. Build 2 to 3 for 4, then 1 to 2 for 5. The total is 9.

Problem D. Packing groups. You have a bag with capacity W. There are g groups of items. Each group is written as k followed by k pairs w v, giving the weight and value of each item in the group. You may take at most one item from each group. Output the largest total value with total weight at most W. Limits: 1 <= W <= 1000, 1 <= g, and the total number of items is at most 300.

Sample input:

10 3
2 4 7 6 9
2 5 8 3 4
1 7 11

Sample output: 15. Take the item of weight 7 and value 11 from the third group, and the item of weight 3 and value 4 from the second group. Total weight 10, total value 15.

Problem E. Tree seating. A tree has n vertices numbered 1 to n and n - 1 edges. Count the sets of exactly m vertices in which no two chosen vertices share an edge. Print the count modulo 1000000007. Limits: 1 <= n <= 300, 0 <= m <= n.

Sample input:

6 3
1 2
1 3
2 4
2 5
3 6

Sample output: 5.

Debrief: solutions

For each problem, do the debugger's check before you read the solution. Write the brute force and run it on the sample. Then compare with your own solution.

Show the answer

Problem A uses prefix sums: one array that stores the count of multiples of 3 up to each position, so any range is answered by subtracting two entries. Tested against a brute force on 400 random cases, with zero mismatches.

#include <bits/stdc++.h>
using namespace std;
// Problem A: count multiples of 3 in a range (prefix sums).
int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    vector<int> pre(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        long long x;
        scanf("%lld", &x);
        pre[i] = pre[i - 1] + (x % 3 == 0 ? 1 : 0);
    }
    while (q--) {
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%d\n", pre[r] - pre[l - 1]);
    }
    return 0;
}

Problem B is the worked problem above. The solution in that section was tested against a brute force on 400 random cases, with zero mismatches.

Problem C is a minimum spanning tree problem. Sort the roads by cost, with existing roads costing 0, then add each road that joins two separate groups of cities, using a union-find structure. Tested against a brute force that tries every subset of new roads on 400 random cases, with zero mismatches.

#include <bits/stdc++.h>
using namespace std;
// Problem C: road repairs. Kruskal with DSU; already-built roads cost 0.
struct DSU {
    vector<int> p;
    DSU(int n) : p(n) { iota(p.begin(), p.end(), 0); }
    int f(int x) { return p[x] == x ? x : p[x] = f(p[x]); }
    bool unite(int a, int b) {
        a = f(a); b = f(b);
        if (a == b) return false;
        p[a] = b;
        return true;
    }
};
 
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    struct E { int u, v; long long c; };
    vector<E> e(m);
    for (auto &x : e) {
        int built;
        scanf("%d %d %lld %d", &x.u, &x.v, &x.c, &built);
        x.u--; x.v--;
        if (built) x.c = 0;
    }
    sort(e.begin(), e.end(), [](const E &a, const E &b) { return a.c < b.c; });
    DSU d(n);
    long long total = 0;
    int used = 0;
    for (auto &x : e)
        if (d.unite(x.u, x.v)) {
            total += x.c;
            used++;
        }
    printf("%lld\n", used == n - 1 ? total : -1LL);
    return 0;
}

Problem D is a knapsack over groups. Keep dp[w] as the best value with total weight at most w. For each group, compute the new table from the old one, so that two items of the same group are never used together.

#include <bits/stdc++.h>
using namespace std;
// Problem D: packing groups. At most one item per group, total weight <= W, maximise value.
int main() {
    int W, g;
    scanf("%d %d", &W, &g);
    vector<long long> dp(W + 1, 0);   // dp[w] = best value with total weight <= w
    for (int i = 0; i < g; i++) {
        int k;
        scanf("%d", &k);
        vector<pair<int, long long>> items(k);
        for (auto &it : items) scanf("%d %lld", &it.first, &it.second);
        vector<long long> nd = dp;     // choosing nothing from this group
        for (auto &[wt, val] : items)
            for (int w = wt; w <= W; w++)
                nd[w] = max(nd[w], dp[w - wt] + val);   // uses old dp, so one item per group
        dp = nd;
    }
    printf("%lld\n", dp[W]);
    return 0;
}

The mistake to avoid here is updating dp in place while looping over the items of one group, because then one group can contribute two of its items to the same total. This solution was tested on 400 random cases, with zero mismatches.

Problem E is tree DP. Root the tree at vertex 1. For each vertex, keep two arrays indexed by the number of chosen vertices in its subtree: one for the case where the vertex is not chosen, and one where it is chosen. A chosen vertex forces its children to be unchosen. Merge the children one at a time. Tested on 400 random trees, zero mismatches.

#include <bits/stdc++.h>
using namespace std;
// Problem E: tree seating. Count sets of exactly m vertices with no two adjacent, mod 1e9+7.
const long long MOD = 1000000007LL;
int n, m;
vector<vector<int>> g;
 
// returns (a, b): a[j] = ways with v not chosen and j chosen in subtree,
//                 b[j] = ways with v chosen and j chosen in subtree.
pair<vector<long long>, vector<long long>> dfs(int v, int par) {
    vector<long long> a = {1, 0}, b = {0, 1};
    for (int c : g[v]) {
        if (c == par) continue;
        auto [ca, cb] = dfs(c, v);
        int sa = a.size(), sc = ca.size();
        vector<long long> na(sa + sc - 1, 0), nb(sa + sc - 1, 0);
        for (int i = 0; i < sa; i++)
            for (int j = 0; j < sc; j++) {
                na[i + j] = (na[i + j] + a[i] * ((ca[j] + cb[j]) % MOD)) % MOD;  // v not chosen: child free
                nb[i + j] = (nb[i + j] + b[i] * ca[j]) % MOD;                   // v chosen: child not chosen
            }
        a = na;
        b = nb;
    }
    return {a, b};
}
 
int main() {
    scanf("%d %d", &n, &m);
    g.assign(n + 1, {});
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    auto [a, b] = dfs(1, 0);
    long long ans = 0;
    if (m < (int)a.size()) ans = (a[m] + b[m]) % MOD;
    printf("%lld\n", ans);
    return 0;
}

Run on the sample, this prints 5. The five sets are {1,4,5}, {1,4,6}, {1,5,6}, {3,4,5} and {4,5,6}.

The cost is O(n^2) in the worst case, which is trivial for n <= 300.

Timeline log

Keep this log during the set, one line per event.

time   role      problem  event               verdict  penalty_so_far
0:00   reader    all      read statements     -        0
0:15   reader    all      plan table written  -        0
0:20   coder     A        start coding        -        0
0:32   coder     A        submit              AC       32
0:40   debugger  C        brute force done    -        32
0:55   coder     C        submit              WA       32
1:05   debugger  C        mismatch found      -        32
1:12   coder     C        submit              AC       124

Replace the last row with your own numbers. The penalty column is the running total under the rule above.

At the end of the set, compare the log with the reader's plan. Write the actual minutes next to each guess. A difference of more than a factor of two means your plan's estimate for that kind of problem needs changing.

Common mistakes

• Typing before the reader has finished. The first 15 minutes are for reading all five statements. Teams that start coding at minute 3 usually spend the rest of the set on the first problem they picked.
• Two people typing into the same file. One person types, the other reads. If both are typing, the file ends up as a mix of two half-written solutions.
• Submitting without a sample run. A symptom you will see: the judge returns WA on the first test, and the team pays 20 minutes of penalty to learn what a sample run would have shown in a few seconds.
• Counting a compile error as a wrong answer in the log. The ICPC help text says a compile error does not carry the 20-minute penalty, so the log should not add one for it. Keep the verdict letter so you can see the difference later.
• Trusting an AI assistant's solution without a brute force. A model can produce code that reads well and passes the sample but fails on a case the sample does not cover. The brute force catches this in seconds. The symptom is a wrong answer on a case the sample did not cover, or a brute force that disagrees with the solution.
• Resubmitting the same code after WA. Each wrong answer adds 20 minutes. The debugger should find the failing input first.
• Forgetting the time-limit check. A solution that is correct but too slow gets TLE, which carries the same penalty as WA. Check the worst case size from the limits before you submit.

Checklist

• Read all statements in the first 15 minutes, and write the plan table before typing.
• Give each problem a value per minute from the plan, and read in that order unless the team agrees otherwise.
• One person types. The others read, test or write the brute force.
• Run the sample, and one small case you check by hand, before every submission.
• Do not submit code that the debugger has not tested on random small inputs.
• After a WA, find the failing input before the next submission.
• Log every submission with its role, minute and verdict.
• At the end, compare the log with the plan and note which estimates were wrong.

Practice

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

Practice 1. Penalty by hand. Your team submits: problem E at minute 20 (WA), E at minute 35 (WA), E at minute 50 (AC), problem F at minute 61 (CE), F at minute 88 (AC), and problem G at minute 100 (TLE). What is the total penalty, and how many problems are solved? Check your answer by running the scoreboard script with these events.

Show the answer

E is solved at minute 50 with 2 wrong answers, so its penalty is 50 + 2 * 20 = 90. F has a compile error at 61 (no penalty) and is accepted at 88, so its penalty is 88. G is never accepted, so it adds nothing even though it had a TLE. The total penalty is 90 + 88 = 178, and 2 problems are solved. Running the script with these events prints problems solved: 2, total penalty: 178.

Practice 2. Order the set. Your reader's table is: problem A, 500 points, 20 minutes, chance 0.80. Problem B, 1000 points, 60 minutes, chance 0.50. Problem C, 750 points, 30 minutes, chance 0.70. Which problem does the ratio say to read first, and what is the expected points per minute for B?

Show the answer

Expected points per minute is points times chance divided by minutes. A gives 500 * 0.80 / 20 = 20.00. B gives 1000 * 0.50 / 60 = 8.33. C gives 750 * 0.70 / 30 = 17.50. The ratio says A first, then C, then B. The expected points per minute for B is 8.33.

Practice 3. Write the brute force for problem A. Write a Python brute force for problem A that reads the same input format and prints one line per query. Test it on the sample, and then compare it with the solution on five random inputs of your own.

Show the answer

A brute force loops over the range for each query and counts the multiples of 3. This is slow, but it is simple enough to trust.

import sys
 
def main():
    data = sys.stdin.read().split()
    n, q = int(data[0]), int(data[1])
    a = [int(x) for x in data[2:2 + n]]
    pos = 2 + n
    out = []
    for _ in range(q):
        l, r = int(data[pos]), int(data[pos + 1])
        pos += 2
        out.append(str(sum(1 for x in a[l - 1:r] if x % 3 == 0)))
    print("\n".join(out))
 
main()

On the sample, this prints 2 and 2, the same as the solution. Use a small generator with n up to 8 and values up to 30, run both programs on the same five inputs, and check that the outputs match. If they differ, the first difference is the input to reduce by hand.

Summary

A team of three with one computer wins by splitting the roles, ordering the problems by expected points per minute, and checking every submission before it reaches the judge. The penalty is the solve minute plus 20 minutes for each wrong answer before the accepted one, and the timeline log shows where the minutes went.