Olympiad-style set 1: subtasks

Why this matters when you build with AI

When an AI assistant writes code for you, it usually aims at the whole job at once. A subtask set asks for something different: a solution that is right on some inputs and wrong on others is still worth points. The same habit helps with AI output. You keep the parts that work, test the new version against every earlier case, and only then move on. This lesson trains that habit on an olympiad-style set of four problems.

This lesson uses the general idea of subtasks and points per hour from the earlier lesson "Partial scores and subtasks". Here the new skill is running a whole set: a scoring plan across four problems, and a regression check (a test that an improvement did not break an older case) for each change.

The idea: a set is four ladders and one budget

In an olympiad, a subtask is a group of tests with its own input limits and its own points. You get the points for a group only when every test in it passes. A limit is a bound such as n <= 3000, where n is the number of items in the input.

A set of four problems gives you four ladders, one per problem, with one clock for the whole set. The clock is the real limit. Each problem has rungs: a cheap rung that only handles small or special inputs, and a top rung that handles the full limits.

Here is the set for this lesson. Every problem is original, and only the first problem is solved in full below.

The rightmost column is what each subtask tells you about the full solution. For example, subtask 2 of Gate Keys says that the answer depends only on the right ends, which points you at the top rung.

Standard technique: plan the points before the code

Write the plan first, on paper or in a file. For each subtask, record three numbers: points, the time you think it takes to write and test, and the chance you will finish it. Then divide points by time.

For a single problem, the order is simple: take the cheapest rung that is safe, then climb. For a set, the order is across problems. A cheap subtask of a second problem can be worth more than the top rung of the first problem, when the top rung is hard for you.

Use this rule for every change you make after the first submission: the new code must pass every test that the old code passed, before you add the new rung. That rule is what keeps a rung from quietly costing an earlier rung its points.

Worked example: Steady Climb

The statement

You are given n values v_1 to v_n and an integer K. Choose indices i_1 < i_2 < ... < i_m with m >= 1, so that the chosen values never go down and every step goes up by at most K. Print the largest m.

Example: n = 5, K = 1, values 1 2 2 3 1. The chain at indices 1, 2, 3, 4 has values 1, 2, 2, 3. Each step is 1, 0 or 1, which is at most K = 1, and no step goes down. So the answer is 4. The index 5 (value 1) cannot follow the value 3, because the step goes down.

Subtask 1: try every subset

For n <= 16 there are at most 2^16 = 65536 subsets. Check each subset in order and keep the largest valid one. This is the brute force: it is slow, but it is simple enough to be trusted, and it becomes the reference the other programs are compared with.

// Subtask 1 (n <= 16): try every subset of indices and keep the largest valid one.
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n;
    long long K;
    cin >> n >> K;
    vector<long long> v(n);
    for (auto &x : v) cin >> x;
 
    int best = 0;
    for (int mask = 1; mask < (1 << n); ++mask) {
        bool ok = true;
        bool first = true;
        long long prev = 0;
        int cnt = 0;
        for (int i = 0; i < n && ok; ++i) {
            if (!(mask >> i & 1)) continue;
            if (!first) {
                long long step = v[i] - prev;
                if (step < 0 || step > K) ok = false;
            }
            first = false;
            prev = v[i];
            ++cnt;
        }
        if (ok) best = max(best, cnt);
    }
    cout << best << "\n";
}

Subtask 3: dynamic programming in O(n^2)

Let dp[i] be the length of the best chain that ends at index i. A chain ending at i either starts at i (length 1), or comes from an earlier index j with v_j <= v_i <= v_j + K, in which case its length is dp[j] + 1. Take the maximum over all j < i.

// Subtask 3 (n <= 3000): dp[i] is the longest valid chain that ends at index i.
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n;
    long long K;
    cin >> n >> K;
    vector<long long> v(n);
    for (auto &x : v) cin >> x;
 
    vector<int> dp(n, 1);
    int best = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (v[j] <= v[i] && v[i] - v[j] <= K) dp[i] = max(dp[i], dp[j] + 1);
        }
        best = max(best, dp[i]);
    }
    cout << best << "\n";
}

Subtask 2: when K = 0

With K = 0, every step must have size 0, because a step cannot go down. So a valid chain repeats one single value. The answer is the largest number of copies of any one value. This program is correct only for inputs where K = 0, and it ignores K on purpose.

// Subtask 2 (K = 0 in every test): a chain with step 0 repeats one value,
// so the answer is the largest number of copies of any single value.
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n;
    long long K;
    cin >> n >> K;
    map<long long, int> copies;
    for (int i = 0; i < n; ++i) {
        long long x;
        cin >> x;
        copies[x]++;
    }
    int best = 0;
    for (auto &p : copies) best = max(best, p.second);
    cout << best << "\n";
}

The hint in subtask 2 matters for the full solution. Equal values chain with any K, so the query range must include v_i itself.

Subtask 4: a segment tree over values

The full limits make the O(n^2) loop too slow. Use the idea from the hint: keep best[w], the longest chain seen so far that ends at value w. For element x, the new chain length is 1 + max(best[x - K] .. best[x]). After computing it, store it at best[x].

A segment tree is a binary tree over an array of positions that answers "maximum over a range" and "change one position" in about log n steps. Here the positions are the values 1 to 10^6, and 2^20 = 1048576 is a power of two that covers them.

// Full solution (n <= 200000, values <= 1000000).
// Process the array left to right. best[w] holds the longest chain seen so far
// that ends at value w. For element x, a chain can come from any earlier value
// in [x - K, x], so dp = 1 + max(best[x - K .. x]). A max segment tree answers that range.
#include <bits/stdc++.h>
using namespace std;
 
const int MAXV = 1 << 20;  // covers values up to 1000000
int tree_[2 * MAXV];
 
void update(int pos, int val) {
    pos += MAXV;
    tree_[pos] = max(tree_[pos], val);
    for (pos >>= 1; pos >= 1; pos >>= 1) tree_[pos] = max(tree_[2 * pos], tree_[2 * pos + 1]);
}
 
int query(int l, int r) {  // inclusive range [l, r]
    int res = 0;
    for (l += MAXV, r += MAXV + 1; l < r; l >>= 1, r >>= 1) {
        if (l & 1) res = max(res, tree_[l++]);
        if (r & 1) res = max(res, tree_[--r]);
    }
    return res;
}
 
int main() {
    int n;
    long long K;
    cin >> n >> K;
    int best = 0;
    for (int i = 0; i < n; ++i) {
        long long x;
        cin >> x;
        int lo = (int)max(1LL, x - K);
        int dp = query(lo, (int)x) + 1;
        update((int)x, dp);
        best = max(best, dp);
    }
    cout << best << "\n";
}

Hand trace on the example

Run the full solution by hand on 1 2 2 3 1 with K = 1. The tree starts empty, so every query returns 0 until something is stored.

The last row is the one to check: the stored value at 1 goes from 1 to 2, because dp = 2 is larger. The largest dp is 4, which matches the program output. The trace values are my hand calculation, and the program prints only the final number.

Running the programs

I compiled every program with g++ -O2 -std=c++17 and ran them on the example. The output lines are real.

cd ~/contest/07
mkdir -p bin
for f in p1_brute p1_quadratic p1_equal p1_full p1_broken; do
  g++ -O2 -std=c++17 -Wall -Wextra -o bin/$f $f.cpp
done
printf '5 1\n1 2 2 3 1\n' | ./bin/p1_full
printf '5 1\n1 2 2 3 1\n' | ./bin/p1_brute
printf '5 1\n1 2 2 3 1\n' | ./bin/p1_quadratic
printf '5 0\n1 2 2 3 1\n' | ./bin/p1_equal
printf '5 0\n1 2 2 3 1\n' | ./bin/p1_broken

4
4
4
2
1

The last two lines show the trap discussed below: the K = 0 program gives 2 (the value 1 and the value 2 each appear twice), and the broken program gives 1.

Stress test against the brute force

Random tests are where small bugs show up. I generated 1000 random inputs with n from 1 to 12, K from 0 to 4 and values from 1 to 6, and compared each program with the brute force. The output is real.

p1_full: 0 mismatches out of 1000 tests
p1_quadratic: 0 mismatches out of 1000 tests
p1_broken: 637 mismatches out of 1000 tests
  first failing input:
  6 1
  4 6 1 1 5 1
p1_equal: 0 mismatches out of 1000 tests

The p1_equal line is 0 mismatches only because the stress test ran it on the K = 0 inputs. A test that runs a program outside its subtask tells you nothing.

Breaking an earlier subtask while improving

Suppose you "clean up" the full solution by changing the query to [x - K, x - 1], so that equal values are excluded. It looks harmless, and it compiles. On 4 0 / 2 2 2 2, the full solution prints 4, and the broken version prints 1, because with K = 0 the range is empty.

The scoring harness below runs every program on the four subtasks and gives each subtask its points only when every test in it matches a reference. The reference for subtasks 1 to 3 is the brute force or the quadratic DP. For subtask 4 the reference is the full solution, because no slow reference can run at n = 200000.

p1_full: score 100 / 100
  subtask 1 (20 pts): PASS - all tests match
  subtask 2 (20 pts): PASS - all tests match
  subtask 3 (30 pts): PASS - all tests match
  subtask 4 (30 pts): PASS - matches full, 0.28s on n=200000
p1_quadratic: score 70 / 100
  subtask 1 (20 pts): PASS - all tests match
  subtask 2 (20 pts): PASS - all tests match
  subtask 3 (30 pts): PASS - all tests match
  subtask 4 (30 pts): FAIL - timeout (over 10 s)
p1_equal: score 20 / 100
  subtask 1 (20 pts): FAIL - wrong: got 3, expected 5
  subtask 2 (20 pts): PASS - all tests match
  subtask 3 (30 pts): FAIL - wrong: got 78, expected 133
  subtask 4 (30 pts): FAIL - wrong: got 4, full solution says 29
p1_brute: score 20 / 100
  subtask 1 (20 pts): PASS - all tests match
  subtask 2 (20 pts): FAIL - wrong: got 0, expected 51
  subtask 3 (30 pts): FAIL - wrong: got 0, expected 133
  subtask 4 (30 pts): FAIL - wrong: got 0, full solution says 29
p1_broken: score 30 / 100
  subtask 1 (20 pts): FAIL - wrong: got 1, expected 2
  subtask 2 (20 pts): FAIL - wrong: got 1, expected 51
  subtask 3 (30 pts): FAIL - wrong: got 30, expected 133
  subtask 4 (30 pts): PASS - matches full, 0.27s on n=200000

The broken program scores 30 points, because it passes subtask 4 by chance. Subtask 4 has only one random test here, so that pass is weak evidence. The full solution scores 100 in this harness, but only the tests in this harness back that up; a judge with other tests can still find a bug. The machine that ran these tests will give different times. The pass and fail lines should not change.

Two things to see in this output. First, the broken edit lost 70 points from subtasks 1 to 3, which a single change to one number caused. Second, the timing for subtask 4 is a single measurement on one machine, so a pass near the 2-second limit is not safe.

Hands-on exercise

Do this on your own machine. You need g++ and Python 3.

1. Save the brute force, the quadratic DP and the full solution from this lesson as three files.
2. Compile each with g++ -O2 -std=c++17.
3. Write a Python stress script that makes 500 random inputs with n from 1 to 12, K from 0 to 4 and values from 1 to 6. Print the number of mismatches for each program.
4. Add a fourth program that is a copy of the full solution with the query changed to [x - K + 1, x]. Predict its mismatch count before you run it. Then run it and compare.
5. Write your own scoring plan for this set. Use the table above, and fill in a column for the minutes you think each subtask takes. Sort the rungs by points per minute.

Keep the answers in your practice log. Note what you predicted and what happened.

Common mistakes

Trusting the sample. The broken program prints 3 for the sample 5 1 / 1 2 2 3 1, where the answer is 4. The sample is one input, so compare with the brute force on random inputs. A small input such as 4 0 / 2 2 2 2 shows the broken program's bug at once: it prints 1, and the answer is 4.

Using a subtask program outside its subtask. The K = 0 program prints 2 on the sample, and the right answer is 4. Use it only on inputs where K = 0, and never as the reference for other tests.

Using 1 << n on large n. In the brute force, 1 << n with int n is undefined behaviour once n is 31 or more. The result is not a reliable number, so the brute force must only run on subtask 1 inputs. When the subtask 4 timing test ran the brute force, it printed 0, which is wrong.

Timing on a fast laptop and trusting the result. A program that takes 0.28 seconds here can take much longer on the judge. Keep a margin of at least two times the limit when you judge a rung safe.

Skipping the regression run. Each change to the full solution must pass the earlier subtasks again. Symptom: points go down after an "improvement" even though the new subtask passes.

Checklist

• Read every subtask row and write the points, the limits and the rung's hint.
• Plan the order of rungs by points per minute, across all four problems.
• Write the brute force first, and use it as the reference for small inputs.
• After each change, run the stress test and every earlier subtask again.
• Compile with -O2 and at least -Wall -Wextra, and read the warnings.
• Time the largest input and keep a margin of at least two times the limit.
• Record predicted and real points for each subtask in your log.

Summary

A subtask set is a budget of time spread over several ladders. Plan the rungs by points per minute, secure the cheap ones first, and use the brute force as the reference for every change. The hints inside each subtask point at the full idea, so read them closely. Most lost points come from a change that breaks an earlier rung, so run every earlier subtask again after each change.

Practice

1. Gate Keys has n, m <= 200000 in the full subtask, and the subtask with all keys starting at gate 1 is worth 25 points. Write the one-line answer for that subtask and the reason it is correct.
2. A student's Steady Climb full solution prints 1 for the input 3 0 / 5 5 5, where the answer is 3. Find the one-line change that causes it, without running the code.
3. For Steady Climb, compute the answer by hand for 4 0 / 3 3 3 4.
4. For Window Inversions, a window of size D means index j may pair with i only when j - D <= i < j. Explain why the Fenwick tree must hold indices j - D to j - 1 when it answers the query for j, and not index j itself.
5. For a scoring plan, a rung worth 30 points takes 40 minutes and a rung worth 20 points takes 15 minutes. Which one do you climb first, and what would change your mind?

Show the answer

1. The answer is max r_j, the largest right end among the keys, or 0 if there are no keys. Each key opens the range [1, r_j], and a union of ranges that all start at 1 is the single range [1, max r_j].
2. The query range excludes x itself. Write query(lo, x - 1) and the range is [x - K, x - 1], which is empty when K = 0. Each dp is then 1, so the answer is 1, not 3. The query range must include x.
3. A valid chain with K = 0 repeats one value. The value 3 appears three times, and 4 appears once, so the answer is 3.
4. The pair (i, j) needs i < j, so index j must not be counted in its own query. Add j to the tree after the query for j. Then the tree holds j - D to j - 1 at the moment of the query.
5. Climb the 20-point rung first. It is about 1.3 points per minute (20 in 15), against 0.75 points per minute for the 30-point rung (30 in 40). Change the order if the 30-point rung is almost finished, or if the 20-point rung needs a tool you have not used before.