Olympiad-style set 2: subtasks

Why this matters when you build with AI

An AI assistant can write a construction that looks right: a list of numbers that matches the sample and seems to follow the rule. Nobody can tell by reading whether it is right for every input, and a subtask judge will find the one input where it is not. A validator is a program that reads the input and the output and says whether the output follows the rules. Writing one is the same habit as testing AI-written code: you define what "correct" means in a way a machine can check, and then you trust the check, not the look of the answer.

This lesson applies that habit to an olympiad-style set of four subtask problems. It assumes the scoring ideas from the lesson "Olympiad-style set 1: subtasks", which covered the scoring plan and the regression check. Here the new parts are constructive problems, a validator, and a subtask that needs a different algorithm from the full solution.

The idea: a constructive problem has many right answers

Some problems ask you to print a construction, and say "print any valid answer". The judge cannot compare your output with one fixed answer. Instead it runs a checker, a program that reads the input and your output and decides whether the output is valid.

Here is the set for this lesson. Only the first two problems are worked in full below.

For Range Order, the best subtask 1 program is not a smaller version of the full program. It uses a different algorithm, and that is the point of this set.

Standard technique: write the checker before the solver

For a construction, write the validator first. A good validator does four things:

1. It checks the number of values, the format and the ranges.
2. It checks every rule the statement gives, one by one, and reports the first failed rule with its position.
3. For small inputs, it searches for a valid answer on its own, so it knows when -1 (no answer) is the right output.
4. It is run on your solver's output for many n, including the largest one.

The validator is not the solver. If you use the same idea to build both, a wrong idea appears in both and the check passes. For the small cases, use a search that does not share the idea.

Worked example 1: Staircase Permutation

The statement

Given n, print a permutation p of the numbers 1 to n, so that the absolute difference of every two neighbours is at least 2. If no permutation has this property, print -1. Any valid answer is accepted.

Finding the pattern

For n = 1 the single number 1 is a valid answer. For n = 2 the two orders are 1 2 and 2 1, and both neighbours differ by 1. So the answer is -1. For n = 3, the number 2 is always next to 1 or 3, or both, and each of those differs from 2 by 1. So the answer is -1 again.

For n >= 4, put the even numbers first in increasing order, then the odd numbers in increasing order. Two neighbours inside the even block differ by 2, two neighbours inside the odd block differ by 2, and the join is the largest even number e next to the number 1. Since n >= 4, the largest even number is at least 4, so e - 1 >= 3. Every neighbour pair differs by at least 2.

The solver

// Staircase permutation: print a permutation p of 1..n where |p_i - p_(i+1)| >= 2 for every i,
// or -1 when no such permutation exists. Any valid answer is accepted.
// Known cases: n = 1 works; n = 2 and n = 3 are impossible; n >= 4 works with
// all the even numbers in increasing order followed by all the odd numbers in increasing order.
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    if (n == 1) {
        cout << "1\n";
        return 0;
    }
    if (n <= 3) {
        cout << "-1\n";
        return 0;
    }
    vector<int> p;
    for (int x = 2; x <= n; x += 2) p.push_back(x);
    for (int x = 1; x <= n; x += 2) p.push_back(x);
    for (size_t i = 0; i < p.size(); ++i) {
        if (i) cout << ' ';
        cout << p[i];
    }
    cout << "\n";
}

I ran the program for n from 1 to 8 (compiled with g++ -O2 -std=c++17). The part before each colon is the n that my loop passed in; the rest is the program's output:

1: 1
2: -1
3: -1
4: 2 4 1 3
5: 2 4 1 3 5
6: 2 4 6 1 3 5
7: 2 4 6 1 3 5 7
8: 2 4 6 8 1 3 5 7

The validator

This validator reads n and the output file. For n <= 8 it tries every permutation, so it knows whether an answer exists. For larger n it checks the output and accepts -1 only for n equal to 2 or 3, which the pattern above proves.

#!/usr/bin/env python3
"""Validator for the staircase permutation problem.
 
Usage: validate_q1.py <n> <output file>
Exit code 0 when the output is acceptable, 1 otherwise.
"""
import itertools
import sys
 
 
def ok_pair(a, b):
    return abs(a - b) >= 2
 
 
def exists(n):
    for perm in itertools.permutations(range(1, n + 1)):
        if all(ok_pair(perm[i], perm[i + 1]) for i in range(n - 1)):
            return True
    return False
 
 
def validate(n, text):
    tokens = text.split()
    if not tokens:
        return "empty output"
    if tokens == ["-1"]:
        if n <= 8:
            return None if not exists(n) else f"printed -1 but a valid answer exists for n = {n}"
        return None if n in (2, 3) else f"printed -1 for n = {n}, but n >= 4 always has an answer"
    try:
        p = [int(t) for t in tokens]
    except ValueError:
        return "output contains a token that is not an integer"
    if len(p) != n:
        return f"expected {n} numbers, got {len(p)}"
    if sorted(p) != list(range(1, n + 1)):
        return "the numbers are not a permutation of 1..n"
    for i in range(n - 1):
        if not ok_pair(p[i], p[i + 1]):
            return f"positions {i + 1} and {i + 2} hold {p[i]} and {p[i + 1]}, which differ by less than 2"
    return None
 
 
if __name__ == "__main__":
    n = int(sys.argv[1])
    with open(sys.argv[2]) as f:
        text = f.read()
    problem = validate(n, text)
    if problem is None:
        print(f"n={n}: OK")
        sys.exit(0)
    print(f"n={n}: INVALID - {problem}")
    sys.exit(1)

Real results of the validator on the solver's output and on three bad files:

n=1: OK
n=2: OK
n=3: OK
n=4: OK
n=5: OK
n=6: OK
n=7: OK
n=8: OK
n=200000: OK
n=4: INVALID - positions 1 and 2 hold 2 and 1, which differ by less than 2
n=3: INVALID - positions 2 and 3 hold 3 and 2, which differ by less than 2
n=4: INVALID - printed -1 but a valid answer exists for n = 4

The n=200000 line checks the solver's output for the largest size, and it says OK. The validator does not know the answer for n above 8, so it relies on the pattern. That is the honest limit of this checker: it proves the output is valid, and it proves -1 only for the small cases.

Worked example 2: Range Order

The statement

You are given an array a of n values and q queries. Each query gives l, r and k, and asks for the k-th smallest value in a[l..r], counting repeats. The guarantee is 1 <= k <= r - l + 1.

Example: n = 5, q = 3, values 3 1 4 1 5. The queries (1, 5, 2), (2, 4, 2) and (3, 5, 3) have answers 1, 1 and 5.

Subtask 1: one count row per value

With values only from 1 to 300, keep a table cnt[v][i], which is how many of a[1..i] equal v. A query looks at the values in order from 1 to 300. For value v, the number of copies inside a[l..r] is c = cnt[v][r] - cnt[v][l-1]. If k <= c, the answer is v. Otherwise subtract c from k and move to the next value.

// Subtask 2 (n <= 5000, values 1..300, q <= 5000): one prefix-count row per value.
// cnt[v][i] = how many of a[1..i] equal v. A query walks the values 1..300 in order
// and stops at the value where the running count reaches k.
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n, q;
    cin >> n >> q;
    const int V = 300;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
 
    vector<vector<int>> cnt(V + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int v = 1; v <= V; ++v) {
            cnt[v][i] = cnt[v][i - 1] + (a[i] == v ? 1 : 0);
        }
    }
 
    while (q--) {
        int l, r, k;
        cin >> l >> r >> k;
        for (int v = 1; v <= V; ++v) {
            int c = cnt[v][r] - cnt[v][l - 1];
            if (k <= c) {
                cout << v << "\n";
                break;
            }
            k -= c;
        }
    }
}

Hand trace of the last query, (3, 5, 3), on the example. The slice is 4 1 5. Value 1 has c = 1, and k = 3 is larger, so k becomes 2. Value 4 has c = 1, and k = 2 is larger, so k becomes 1. Value 5 has c = 1, and k = 1 fits, so the answer is 5.

The table has n * 300 entries. For n = 5000 that is 1.5 million counts, which is about 6 MB with 4-byte integers. Each query costs about 300 steps, so 5000 queries cost about 1.5 million steps. Both numbers are small, which is why this subtask is cheap to write and fast to run.

The full solution: a persistent tree over sorted values

The table cannot hold values up to 10^9. Compress the values first: sort the distinct values and replace each one with its position in that sorted list. Now the values are 0 to m - 1, where m is the number of distinct values.

A segment tree over positions 0 .. m-1 stores a count in each node. A persistent segment tree keeps the old versions when you change it. Version i holds the counts of a[1..i]. When you add one value, only the nodes on one root-to-leaf path are copied, so each version costs about log m new nodes.

For a query, take version r and version l - 1. Their difference holds the counts of a[l..r]. At each node, compare k with the count in the left child (the difference of the two versions), and go left or right.

// Full solution (n, q <= 200000, values up to 10^9).
// Persistent segment tree over the compressed values. Version i holds the counts of a[1..i].
// The k-th smallest in [l, r] walks down from version r and version l - 1 together,
// comparing how many values sit in the left half of each range.
#include <bits/stdc++.h>
using namespace std;
 
struct PersistentTree {
    vector<int> lc, rc, cnt;
 
    PersistentTree(size_t expected) {
        lc.reserve(expected);
        rc.reserve(expected);
        cnt.reserve(expected);
        newNode(0, 0, 0);  // node 0 is the empty tree: children point to itself
    }
 
    int newNode(int l, int r, int c) {
        lc.push_back(l);
        rc.push_back(r);
        cnt.push_back(c);
        return (int)cnt.size() - 1;
    }
 
    // Returns the root of a new version that is the old version prev plus one value at pos.
    int insert(int prev, int lo, int hi, int pos) {
        int cur = newNode(lc[prev], rc[prev], cnt[prev] + 1);
        if (lo == hi) return cur;
        int mid = (lo + hi) / 2;
        if (pos <= mid) {
            int child = insert(lc[prev], lo, mid, pos);
            lc[cur] = child;
        } else {
            int child = insert(rc[prev], mid + 1, hi, pos);
            rc[cur] = child;
        }
        return cur;
    }
 
    // a is the root for prefix l - 1, b is the root for prefix r. Returns the compressed index.
    int kth(int a, int b, int lo, int hi, int k) const {
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            int leftCount = cnt[lc[b]] - cnt[lc[a]];
            if (k <= leftCount) {
                a = lc[a];
                b = lc[b];
                hi = mid;
            } else {
                k -= leftCount;
                a = rc[a];
                b = rc[b];
                lo = mid + 1;
            }
        }
        return lo;
    }
};
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
 
    vector<long long> vals(a.begin() + 1, a.end());
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    int m = (int)vals.size();
 
    PersistentTree tree((size_t)n * 20 + 5);
    vector<int> root(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        int pos = (int)(lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin());
        root[i] = tree.insert(root[i - 1], 0, m - 1, pos);
    }
 
    while (q--) {
        int l, r, k;
        cin >> l >> r >> k;
        int idx = tree.kth(root[l - 1], root[r], 0, m - 1, k);
        cout << vals[idx] << "\n";
    }
}

The brute force for testing sorts each slice and reads position k. It is slow, but nothing in it can go wrong in a subtle way.

// Brute force: copy the range, sort it, read the k-th value. O(n log n) per query.
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n, q;
    cin >> n >> q;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    while (q--) {
        int l, r, k;
        cin >> l >> r >> k;
        vector<long long> part(a.begin() + l, a.begin() + r + 1);
        sort(part.begin(), part.end());
        cout << part[k - 1] << "\n";
    }
}

Testing and timing

I compiled every program with g++ -O2 -std=c++17 -Wall -Wextra. On the example all three print the same three lines: 1, 1, 5.

I then ran a random stress test. Each small test had n from 1 to 12, up to 8 queries, and a random k inside each range. I compared the subtask 1 program and the full program with the brute force. The output is real.

q2_sub mismatches: 0 out of 400 small tests (values 1..6)
q2_full mismatches: 0 out of 800 tests (small n, values 1..6 and 1..10^9)

Timing on this WSL machine, which was under heavy load (load average above 20 on 12 cores):

• The subtask 1 program on n = 5000, q = 5000: 0.08 seconds.
• The full program on n = q = 200000, values up to 10^9: between 1.3 and 2.8 seconds over four runs.

The full-solution time is close to a 2-second limit on this slow, busy machine. Those numbers describe this machine, not a judge. A faster machine or a quieter one will give different times, and the algorithm, not the timing, is the reason to choose it.

Complexity

• Subtask 1: building the table costs O(n * V), and each query costs O(V). With V = 300 both are small.
• Full: building the tree costs O(n log n), and each query costs O(log n). The tree uses about n * (log n + 1) nodes, which is around 3.8 million for n = 200000.

Common mistakes

Off-by-one in k. Writing k < c instead of k <= c makes the walk skip the right value. I changed the comparison in a copy of the subtask 1 program and ran it on the example. It printed 3 and 4 and then nothing for the third query, because the walk ran past value 300 without a match. Symptom: fewer output lines than queries.

Using the table for large values. Indexing cnt by a value up to 10^9 needs a table with 10^9 rows. A table that size cannot be allocated on a usual machine, so the program fails before the first query.

Reading the wrong version. Querying with root[l] instead of root[l - 1] leaves out a[l] from the difference, so the counts are for a[l+1..r] and the answer can shift. Check the tree on the example before you trust it on big tests.

Strategy under a fixed total time

A set has one clock and several problems. Plan it before you start, with three numbers per subtask: the points, the minutes you think it takes, and how sure you are. Then order the work by points per minute, and leave time at the end for the checks.

For the set in this lesson, suppose you have 150 minutes. These are example estimates for planning, not measurements:

Steps 2 to 5 earn 150 points for about 60 minutes of writing. Step 6 is the longest and most useful step, but it is worth 70 points and may not finish. The plan keeps step 6 after the cheap steps, so a late finish does not cost the easy points.

Partial scores work in your favour in one way: a wrong answer on a subtask removes only that subtask's points. It does not remove the points from the other subtasks. What could go wrong is the opposite: a change to one program that breaks a passing subtask. Re-run every earlier subtask after each change, as the set 1 lesson showed.

Hands-on exercise

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

1. Save the Staircase solver and the validator from this lesson.
2. For n from 1 to 8, write each solver output to a file and run the validator on it.
3. Write three bad output files for n = 5: one with a repeated number, one with an adjacent pair that differs by 1, and one with -1. Run the validator on each and read its message.
4. Save the Range Order brute force, the subtask 1 program and the full program.
5. Write a stress script that makes 300 random tests with n from 1 to 12, values from 1 to 6, and random queries. Count the mismatches for each program.
6. Time the subtask 1 program on n = q = 5000 and the full program on n = q = 200000. Record the machine's load (cat /proc/loadavg on Linux) with each time.

Keep your numbers in your practice log.

Checklist

• Write the validator before the solver, and make it reject a known wrong output.
• For small inputs, make the validator search on its own, without the solver's idea.
• Check every rule of the statement, and report the first one that fails.
• Run the validator on the largest n too.
• For a subtask with a different algorithm, write down why the full idea does not help it.
• Compress large values before you build an array over them.
• Plan the order of subtasks by points per minute, and leave time for re-running the earlier ones.

Summary

A constructive problem needs a validator, because many outputs are right and only a rule check can tell them apart. A subtask can be worth points even when its algorithm is different from the full one, as the table approach shows for Range Order. Under a fixed total time, plan the cheap subtasks first, and re-run every earlier subtask after each change.

Practice

1. For n = 5, the solver prints 2 4 1 3 5. Check every neighbour pair by hand, then say what a swap of the last two numbers (2 4 1 5 3) does to the check.
2. The subtask 1 table for Range Order uses 300 * (5000 + 1) integers. Work out the size in megabytes with 4-byte integers, and say why it fits.
3. Using the example in Range Order, compute the answer to the query (2, 4, 2) by hand with the subtask 1 walk.
4. Explain in two sentences why the full solution uses a persistent tree and not one tree that changes as r grows.
5. A set has 120 minutes and two subtasks: subtask A gives 20 points for 10 minutes, subtask B gives 70 points for 90 minutes. Which one do you do first, and what would change the order?

Show the answer

1. Pairs of 2 4 1 3 5: |2 - 4| = 2, |4 - 1| = 3, |1 - 3| = 2, |3 - 5| = 2. All pass. The swap 2 4 1 5 3 has pairs |1 - 5| = 4 and |5 - 3| = 2, so it also passes. Any pair that differs by 1, such as 2 and 3 next to each other, fails.
2. 300 * 5001 = 1500300 integers, and at 4 bytes each that is about 6.0 MB. Check the memory limit of your contest before you rely on it fitting.
3. The slice a[2..4] is 1 4 1. Value 1 has c = 2, and k = 2 fits, so the answer is 1.
4. Each version of a persistent tree is a full view of the counts for one prefix, and the old versions stay usable. A single changing tree would lose the version for l - 1 once r moved on, so a query for an earlier range could not be answered.
5. Subtask A first: about 2 points per minute (20 in 10). Subtask B is about 0.8 points per minute (70 in 90). Change the order if subtask B is already partly written and only needs checking, or if subtask A needs an idea you have not yet verified.