Partial scores and subtasks

Why this matters when you build with AI

An AI assistant can write a fast solution in seconds. It can also write a solution that is right for small inputs and wrong for large ones, or right for general inputs and wrong when all values are equal. When you use AI on an olympiad-style problem, the first question is not "is the code correct?" but "which part of the score can this code earn?" A solution that passes the small subtasks earns points even when the full solution is still missing.

Olympiad-style contests (the International Olympiad in Informatics and its national rounds, for example) split the tests into groups called subtasks. Each group has its own input limits and its own points. You get the points for a group only when every test in it passes. This gives you a ladder: the simple solutions are worth points on their own, and the fast solution is the top rung.

This lesson teaches the ladder. You will read a subtask table, decide which rungs to climb and in what order, and see how an AI-written solution can fail one rung while passing another.

The idea: a subtask table is a map of the easy cases

A subtask table lists each group of tests with its limits and points. Here is a made-up table for a problem named "Exact train" (you will meet it in the worked example below):

Three words in the table need a definition. N is the size of the input, here the number of cars in a row. A weight is the value attached to each item, here how heavy each car is. Weights ≥ 0 means each weight is zero or more, and weights ≥ 1 means each weight is at least one, so no weight is zero.

Three things to read in a table

Read each row for three things.

1. The limit on N. It tells you the time you can spend. With N = 60, even N³ (about 216000 steps) is instant. With N = 200000, N³ is about 8 × 10¹⁵ steps, far too many for any contest time limit. As a rule of thumb, a contest machine handles about 10⁸ to 10⁹ simple steps in a few seconds, but check the limits of your own judge.

2. The extra restriction. Rows 2 and 3 say "weights ≥ 0" and "weights ≥ 1". Those are structures you can use. If every weight is positive, the prefix sums (running totals) are strictly increasing, and that makes a search much easier. Restrictions like this are often the key to the middle subtasks.

3. The points. A row worth 60 points is worth more than the other two rows added together. Points are not a reward for speed; they are a reward for passing tests.

Why the ladder works

Each subtask is a separate test group. A solution that is too slow for subtask 3 still passes subtask 1 and gets 10 points. Your job is to earn the most points for the time you have. The full solution is only worth writing when you can finish it. If you cannot, the subtasks below it are a safe place to put your time.

Harvesting points from brute force

A brute force is a simple program that tries every possibility. It is slow, but it is usually correct, and it is the cheapest way to earn the first subtask. Write it first, submit it, and see the score. The brute force also gives you a reference: you can compare any faster idea against it on small inputs, as the lesson on stress testing describes.

A brute force is only worth a subtask if its running time fits that subtask's limit. Count the steps before you submit. With N = 60 a triple loop is fine. With N = 3000 a triple loop is about 2.7 × 10¹⁰ steps and will not finish.

Planning with points per hour

Points per hour is a simple way to choose. For each subtask, estimate the points and the time to write and test it, then divide. For example, if you estimate subtask 1 at 10 points and 10 minutes, that is 60 points per hour. If you estimate subtask 2 at 30 points and 25 minutes, that is about 72 points per hour. These numbers are estimates. Your own times will differ, and you should record them in your practice log so the estimates improve.

Points per hour is not the only rule. A subtask you can write in five minutes but that is worth 10 points is a fine early target. A subtask that needs a tricky idea you have not seen before may take much longer than you think. Start with the cheap, safe rungs, then decide whether the top rung is still within reach.

Standard technique: from the cheapest rung to the full solution

Work the ladder from the bottom. For each rung, ask three questions: what does the rung's limit allow, what is the simplest method that fits, and what extra structure does the restriction give.

Rung 1: try everything

If N is at most a few dozen, you can check every block of cars and add its weights one by one. This is O(N³) time (N to the power 3), which is fine for N ≤ 60.

#include <bits/stdc++.h>
using namespace std;
// Subtask 1 (N <= 60): try every block [l, r] and add its weights one by one.
int main() {
    int n;
    long long s;
    cin >> n >> s;
    vector<long long> w(n);
    for (auto& x : w) cin >> x;
    long long count = 0;
    for (int l = 0; l < n; l++)
        for (int r = l; r < n; r++) {
            long long sum = 0;
            for (int i = l; i <= r; i++) sum += w[i];
            if (sum == s) count++;
        }
    cout << count << '\n';
}

Here l and r are the first and last car of a block. Indexes start at 0, so the first car is w[0]. A block must contain at least one car, so r starts at l. The answer counts blocks whose total weight is exactly s.

Rung 2: fix the left end, grow to the right

With weights ≥ 0, a block's total never goes down when you add a car. So for a fixed left end, you can add cars one at a time, and the moment the total passes s, no longer block from this left end can match. That gives O(N²) time, which is fine for N ≤ 3000.

#include <bits/stdc++.h>
using namespace std;
// Subtask 2 (N <= 3000, any weights >= 0): fix the left end, grow the block to the right.
int main() {
    int n;
    long long s;
    cin >> n >> s;
    vector<long long> w(n);
    for (auto& x : w) cin >> x;
    long long count = 0;
    for (int l = 0; l < n; l++) {
        long long sum = 0;
        for (int r = l; r < n; r++) {
            sum += w[r];
            if (sum == s) count++;
            if (sum > s) break;  // weights >= 0 means the sum never comes back down
        }
    }
    cout << count << '\n';
}

The break is the restriction at work. It relies on the weights being zero or more. If a weight could be negative, the total could come back down, and the break would lose blocks. Keep that in mind: the same trick is wrong in a different problem.

Rung 3: use the restriction that all weights are positive

Now take the table's third row: every weight is at least 1. Define the prefix sum p[i] as the total of the first i cars, with p[0] = 0. A block of cars from position i + 1 to j has total p[j] - p[i]. Because each weight is at least 1, the prefix sums are strictly increasing. So for a given start i, there is at most one j with p[j] = p[i] + s, and binary search finds it.

#include <bits/stdc++.h>
using namespace std;
// Subtask 3 (N <= 200000, all weights >= 1): prefix sums are strictly increasing,
// so for each start i there is at most one end j with p[j] - p[i] == s.
int main() {
    int n;
    long long s;
    cin >> n >> s;
    vector<long long> p(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        long long w;
        cin >> w;
        p[i] = p[i - 1] + w;
    }
    long long count = 0;
    for (int i = 0; i <= n; i++) {
        long long target = p[i] + s;
        auto it = lower_bound(p.begin(), p.end(), target);
        if (it != p.end() && *it == target && (it - p.begin()) > i) count++;
    }
    cout << count << '\n';
}

lower_bound returns the first position whose value is at least target. Because the array is strictly increasing, that position holds the value target exactly when a match exists. The check (it - p.begin()) > i makes sure the block is not empty.

The full solution: zeros are allowed

The full problem allows weights of zero. Then the prefix sums are only non-decreasing, so one value can appear many times, and the matches for a start i form a contiguous range. Binary search finds the first and the last position of that range, and we count the positions after i.

#include <bits/stdc++.h>
using namespace std;
// Full solution (N <= 200000, weights >= 0). Prefix sums p[0..n] are not decreasing,
// so the equal values of p form one contiguous range that binary search can find.
int main() {
    int n;
    long long s;
    cin >> n >> s;
    vector<long long> p(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        long long w;
        cin >> w;
        p[i] = p[i - 1] + w;
    }
    long long count = 0;
    for (int i = 0; i <= n; i++) {
        long long target = p[i] + s;
        int lo = lower_bound(p.begin(), p.end(), target) - p.begin();
        int hi = upper_bound(p.begin(), p.end(), target) - p.begin();  // exclusive
        int from = max(lo, i + 1);                                     // need j > i
        if (from < hi) count += hi - from;
    }
    cout << count << '\n';
}

The proof idea is short. Since no weight is negative, p never goes down, so every value appears in one run of adjacent positions. lower_bound and upper_bound give the start and the end of that run. Positions j must be greater than i, which is what max(lo, i + 1) enforces.

Worked example: "Exact train"

Here is an original problem written for this lesson.

There are N train cars in a row. Car i has weight w_i, and every weight is a whole number from 0 to 10^9. A block is a non-empty run of neighbouring cars. You are given a number S. Count the blocks whose total weight is exactly S. The first line holds N and S. The second line holds the N weights. Limits: 1 <= N <= 200000, 0 <= S <= 10^15.

The answer can be as large as about N²/2 (about 2 × 10¹⁰ for N = 200000), so it needs a 64-bit type. Read the statement twice before you start. "Non-empty" means a block has at least one car, and the weights may be zero.

For the sample input:

5 5
2 3 1 4 2

The blocks with total 5 are the cars 2 and 3 (weights 2 and 3) and the cars 1 and 4 (weights 1 and 4). The answer is 2. Check the sample by hand before you trust any code. We did, and each program below prints 2.

Running all four rungs on the sample

We compiled each program with g++ -O2 -std=c++17 and ran it on the sample. Every program printed the same answer.

cubic:     2
quadratic: 2
positive:  2
full:      2

This is one input. Passing a sample does not show that a rung is correct. The test in the next section does that.

Testing against each other

We wrote a random generator. With a seed (a number that fixes the random sequence) it prints a small input, with N from 1 to 40. For odd seeds the weights are 0 to 3, so zeros appear. For even seeds the weights are 1 to 4, so every weight is positive, and then we also run the rung 3 program. A checker ran 400 seeds. It compared the full solution with the rung 1 and rung 2 programs on every input, and with the rung 3 program on the positive inputs. That is 1000 comparisons, with 0 mismatches.

This does not prove the programs correct for all inputs. It shows that the four programs agree on 400 small random cases. The argument for the full solution is the proof idea above, and the testing is a second check on it.

Complexity

On one Linux machine (WSL2, g++ 15.2, -O2) the full solution took about 0.05 seconds for a random input with N = 200000. Your machine will give a different number, so treat that timing as one data point.

Hands-on exercise

Write your own version of rung 2 and rung 3 from the descriptions above, without looking at the code in this lesson. Then test them against the full solution. Write a small generator of your own that prints the same shape: a first line with N and S, and a second line with the weights.

Here is a prompt you can give an AI tool to help you check your work. Use it after you have written your own code, not instead of writing it.

I have a C++17 program for this problem: [paste the statement].
My program is for subtask 2 (N <= 3000, weights >= 0).
Do not rewrite the program. List every assumption it makes about the input
(sizes, signs, whether weights can be zero, whether the answer fits in
a 32-bit integer). For each assumption, give one input that breaks the
program if the assumption fails, and say whether the statement allows that input.

A good answer names the break on the running sum, the int versus long long choice, and the zero-weight case. It gives concrete inputs such as 3 0 followed by 0 0 0. Check each claimed input by running it, because an AI tool can name a failing input that does not actually fail.

Show the answer

Your code should print 2 on the sample. For random tests, your rung 2 program should agree with the full solution on every input with weights ≥ 0. Your rung 3 program should agree with the full solution on every input with weights ≥ 1, and it should disagree with the full solution on an input that has a zero weight. For example, with 3 0 followed by 0 0 0, the full solution prints 6, because all six blocks have total 0. The rung 3 program prints 0, because its binary search finds no block when the prefix sums repeat.

Common mistakes

Using int for the total. Each weight can be 10^9, so three cars already give a total of 3 × 10^9, which is larger than the largest 32-bit signed integer (about 2.1 × 10⁹). We ran a version with an int running sum on the input 3 3000000000 followed by 1000000000 1000000000 1000000000. It printed 0. The full solution printed 1. The sum wrapped around to a negative number, so the match was lost. The symptom on a judge is a wrong answer on large tests only, while the small tests pass.

Using the rung 3 program on zero weights. A solution that is correct for positive weights can be wrong for zero weights, because the prefix sums stop being strictly increasing. On the input 3 0 with 0 0 0, the rung 3 program printed 0 and the full solution printed 6. The symptom is a partial score: the subtask with positive weights passes, and the full subtask fails.

Forgetting that a block is non-empty. If you count the pairs i <= j instead of i < j, you count the empty block. With S = 0, every position then matches itself. The symptom is an answer that is too large by exactly N + 1 when S = 0.

Breaking early when weights can be negative. The break in rung 2 is only correct with weights ≥ 0. A problem with negative weights needs a different method.

Writing the full solution first. The full solution is the hardest rung. If you spend an hour on it and it fails, you may have no points. Write rung 1 first, submit it, and then move up.

Trusting an unordered hash map without thinking. A hash map gives expected O(1) lookups and is a common AI choice for this kind of counting. Its speed depends on the hash function, and a judge can use inputs that make many keys collide. The sorted-prefix method above needs no hashing.

Checklist

• Read every row of the subtask table: N, extra restrictions, points.
• Count steps for each rung against its limit before you write code.
• Write the cheapest rung first, submit it, and record the score.
• Note which restriction (sign of weights, equal values, small N) each rung uses.
• Compute points per hour from your own estimates, and record the real time after each subtask.
• Use 64-bit integers for totals and answers.
• Test each faster rung against the brute force on random small inputs, including zeros and equal values.
• Check the answer on the sample and on a single-element input.

Summary

Subtasks are a ladder of test groups with their own limits and points. Each rung gives points on its own, so a simple method that fits a small limit is worth writing. Read the limits and the extra restrictions in the table, because restrictions such as positive weights unlock faster methods. Plan the order by points per hour, using your own time estimates, and climb as far as your time allows.

Practice

Each practice problem is original. Work on paper or in code, then check the answer section.

1. Points table. Use the table in this lesson, with your own time estimates: subtask 1 takes 10 minutes, subtask 2 takes 25 minutes and subtask 3 takes 50 minutes. Plan A does subtasks 1, 2 and 3 in that order. Plan B does subtask 3 alone. Which plan scores more in 90 minutes? Give the points per hour for each subtask, and say what you assumed.

2. Count the steps. A subtask allows N ≤ 500. Is a method with about N³/6 steps safe? About how many steps is that, and what is the rough running time on a machine that does about 10⁹ simple steps per second?

3. Implement two rungs. Choose any two rungs from this lesson and write them yourself. Test each against the full solution on 200 random inputs with N from 1 to 40, including zero weights for the rung 2 test.

4. Find the wrong line. This code is meant for the full problem. It fails on some inputs. Find the bug and give a small input that shows it.

   Copy

   int main() {
       int n; long long s; cin >> n >> s;
       vector<long long> p(n + 1, 0);
       for (int i = 1; i <= n; i++) { long long w; cin >> w; p[i] = p[i - 1] + w; }
       long long count = 0;
       for (int i = 0; i <= n; i++) {
           long long target = p[i] + s;
           if (binary_search(p.begin(), p.end(), target)) count++;
       }
       cout << count << '\n';
   }

5. Restricted structure. Suppose every weight is either 0 or 1. Describe a method that runs in O(N) time and counts the blocks with total exactly S. Hint: think about how many prefix sums of each value there are.

Show the answer

1. Plan A takes 10 + 25 + 50 = 85 minutes and scores 10 + 30 + 60 = 100 points, so it fits in 90 minutes. Plan B takes 50 minutes and scores 60 points, and the last 40 minutes are unused. Points per hour: subtask 1 is 10 / (10 / 60) = 60, subtask 2 is 30 / (25 / 60) = 72, subtask 3 is 60 / (50 / 60) = 72. The ranking follows from your own estimates, so change the minutes and recheck.

2. About N³/6 with N = 500 is 500³ / 6, about 2.1 × 10⁷ steps. At 10⁹ steps per second that is about 0.02 seconds. Such a method is safe for this limit with a large margin.

3. Your two rungs should agree with the full solution on every random test where their limits and restrictions hold. The rung 2 test must include zero weights, and the rung 3 test must use only positive weights.

4. The bug: binary_search only says whether a value exists, so each start i adds at most 1. It also counts j values that are not after i, including j = i itself. On the input 3 0 with 0 0 0, the program printed 4, and the full solution printed 6. The full solution counts every position j > i that matches, which is 3 + 2 + 1 = 6 here. The fix is the lower_bound and upper_bound pair from the full solution, plus the max(lo, i + 1) step.

5. With weights 0 or 1, the prefix sums rise by 0 or 1 at each step, so their values stay between 0 and N. Keep an array cnt of size N + 1, where cnt[v] is the number of positions seen so far with prefix value v. Start with cnt[0] = 1 for p[0] = 0. For each j from 1 to N, let v = p[j] - S. If v is at least 0, add cnt[v] to the answer, then add 1 to cnt[p[j]]. This scans the array once, so it runs in O(N) time.