Problem set

Why this matters when you build with AI

An AI tool will answer a range problem with a segment tree almost every time, because that is the tool it has seen most. A segment tree is correct for many problems, so the answer often passes the sample. It can still be the wrong choice. It may be too slow for the limits, too heavy in memory, or unable to handle the operation (a segment tree cannot answer distinct counts directly, for example, without extra work).

The skill in this lesson is the choice. For each problem, you name the tool first, say why the other tools do not fit, and then test the code against a brute force. A brute force is a slow program that is obviously correct, such as a loop over every element. When the fast program and the brute force give the same answers on many random small inputs, you have evidence. When they differ, you have a bug, and the brute force shows the smallest input that breaks it.

Ask an AI tool to explain its choice of tool in one paragraph. A good answer names the operation and the limit that rules out the naive approach. A weak answer says "a segment tree is efficient" and gives no limit. Check the answer by running the brute force on the sample it gives you.

How to use this set

Each problem has the same parts:

1. A statement with input format, limits, and a sample.
2. A brute force in C++17. Copy it into a file, compile it with g++ -O2 -std=c++17, and check it on the sample.
3. A random generator spec. Write the generator yourself from the spec, so the test does not depend on the answer.
4. An editorial under "Show the answer". Open it only after you have written your own solution, or after an hour of work.

Work in a folder of your own. Keep the brute force and the generator in separate files, so you can rerun the test after each change.

The limits in the statements are the ones the choice depends on. The samples and random tests are small so that you can check them by hand. Do not treat a passing random test as proof of speed. To check speed, generate inputs at the full limit and time your program on your own machine. Your timings will differ from anyone else's.

Shared header for the brute forces

All brute forces below use the same few includes and types. Put this block at the top of each brute force file:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
struct Up1 { int l, r; ll x; };         // P1 update: add x to positions l..r
struct Q2 { int l, r; };                // P2 query, 0-based. P5 and P6 use Q5, which has the same shape
struct Q5 { int l, r; };                // P5 and P6 query, 1-based
struct Op3 { int type; int p; ll d; };  // P3: type 1 adds d at p; type 2 uses d as S
struct Op4 { int type; int a, b; ll v; };  // P4: type 1 sets a to v; type 2 queries [a, b]
struct Op8 { int type; int from; ll x; int k; };  // P8: type 1 inserts x into version from; type 2 asks k-th in version from

Choosing the tool

The table gives the tool that fits each problem and the limit that decides it. Do not read the table until you have chosen your own tool for a problem.

Read the table with care. For problem 2, a segment tree is also within the limit on paper: a sparse table answers each query in O(1), a segment tree in O(log n), which is about 4 * 10^6 steps for 200000 queries. The sparse table is the better fit, but the limit does not rule out the segment tree. For problem 4, lesson 08 covers sqrt decomposition, which this set does not test, so the table does not claim it. For problem 6, the reason for Mo's is the operation: the number of equal pairs changes in a simple way when one element is added or removed, but a sparse table cannot combine two overlapping blocks for a count of pairs.

Problem 1: Night shifts

A hospital has N shifts in a row, numbered 1 to N. There are Q changes. Each change adds x to every shift from l to r, inclusive. After all changes, print the value of every shift.

Input: the first line has N and Q. Each of the next Q lines has l r x. Limits: N and Q up to 200000, x between -10^9 and 10^9, and all sums fit in a 64-bit integer. Output: N numbers on one line, separated by spaces.

Sample input:

5 3
1 3 2
3 5 -1
2 2 4

Sample output:

2 6 1 -1 -1

The brute force adds x to each shift in the range one at a time. It is O(N * Q) in the worst case:

vector<ll> brute1(int n, const vector<Up1>& ups) {
    vector<ll> a(n + 2, 0);
    for (auto u : ups) for (int i = u.l; i <= u.r; i++) a[i] += u.x;
    return vector<ll>(a.begin() + 1, a.begin() + n + 1);
}

Generator spec: n is random from 1 to 20. q is random from 0 to 20. For each update, l is random from 1 to n, r is random from l to n, and x is random from -10 to 10. Run 1500 cases.

Show the answer

Use a difference array. Keep an array d of length N + 2. To add x to [l, r], do d[l] += x and d[r + 1] -= x. At the end, the value of shift i is the running sum of d[1] through d[i]. Each update costs O(1), and the final pass costs O(N). The total is O(N + Q), which is far below the O(N * Q) of the brute force at the limit. A segment tree with lazy tags also works, but it does more work than this problem needs.

Problem 2: Window gcd

You have an array a of N positive integers, indexed from 0. There are Q queries. Each query gives l and r, and asks for the greatest common divisor of a[l] through a[r], inclusive.

Input: the first line has N and Q. The second line has the N values. Each of the next Q lines has l r, with 0-based indexes. Limits: N and Q up to 200000, each value between 1 and 10^9. Output: one answer per line.

Sample input:

6 4
12 18 8 27 30 45
0 2
2 5
3 5
0 0

Sample output:

2
1
3
12

The brute force loops over the range for each query. It is O(N * Q) at the limit:

vector<ll> brute2(const vector<ll>& a, const vector<Q2>& qs) {
    vector<ll> out;
    for (auto q : qs) { ll g = 0; for (int i = q.l; i <= q.r; i++) g = __gcd(g, a[i]); out.push_back(g); }
    return out;
}

Generator spec: n is random from 1 to 30. Each value is random from 1 to 60. Up to 30 queries, each with l random from 0 to n - 1 and r random from l to n - 1. Run 1500 cases.

Show the answer

Build a sparse table with st[k][i] = gcd(st[k - 1][i], st[k - 1][i + 2^(k - 1)]). A query [l, r) uses the two blocks of length 2^k where 2^k is the largest power that fits, as in lesson 02. The gcd is idempotent, since gcd(x, x) = x, so the two overlapping blocks give the right answer. The build is O(N log N), and each query is O(1). The reference solution in the test harness matched the brute force on 1500 random cases.

Problem 3: Prefix target

You have an array a of N non-negative integers, indexed from 1. There are Q operations, of two kinds.

• 1 p d: add d to a[p]. The value stays non-negative.
• 2 S: print the smallest index i such that a[1] + ... + a[i] >= S, or -1 if no such index exists.

Input: the first line has N and Q. The second line has the N values. Then Q lines, each in one of the two forms. Limits: N and Q up to 200000, values up to 10^9, S up to 10^15. Output: one answer per line for each type 2 operation.

Sample input:

4 4
1 2 3 4
2 4
1 1 5
2 7
2 100

Sample output:

3
2
-1

The brute force scans the prefix sums from the start for each type 2 operation:

vector<ll> brute3(int n, const vector<ll>& init, const vector<Op3>& ops) {
    vector<ll> a = init; vector<ll> out;
    for (auto o : ops) {
        if (o.type == 1) a[o.p] += o.d;
        else {
            ll s = 0; ll ans = -1;
            for (int i = 1; i <= n; i++) { s += a[i]; if (s >= o.d) { ans = i; break; } }
            out.push_back(ans);
        }
    }
    return out;
}

Generator spec: n is random from 1 to 20. Initial values are random from 0 to 9. For each operation, with probability one half make a type 1 update: p is random from 1 to n, and d is random from -a[p] to 9, so the value stays at least 0. Otherwise make a type 2 query with S random from 1 to the current total plus 5. Up to 30 operations. Run 1500 cases.

Show the answer

Use a Fenwick tree (lesson 03) and walk down it. Start with pos = 0 and the remaining target rem = S. For each power of two b from the highest down to 1, if pos + b <= N and the tree value at pos + b is smaller than rem, move pos to pos + b and subtract that tree value from rem. At the end, pos + 1 is the answer, or -1 if pos + 1 is past N. This works because all values are non-negative, so the prefix sums never decrease. Each operation costs O(log N). The reference solution matched the brute force on 1500 random cases.

Problem 4: Best window with edits

You have an array of N integers, indexed from 1. There are Q operations.

• 1 p v: set a[p] to v.
• 2 l r: print the largest sum of a non-empty contiguous part of a[l] .. a[r].

Input: the first line has N and Q. The second line has the N values. Then Q lines. Limits: N and Q up to 200000, values between -10^9 and 10^9. Output: one answer per line for each type 2 operation.

Sample input:

5 4
2 -3 4 -1 2
2 1 5
1 2 10
2 1 5
2 3 4

Sample output:

5
17
4

The brute force runs Kadane's method over the range for each query:

vector<ll> brute4(const vector<ll>& init, const vector<Op4>& ops) {
    vector<ll> a = init; vector<ll> out;
    for (auto o : ops) {
        if (o.type == 1) a[o.a] = o.v;
        else {
            ll best = LLONG_MIN, cur = 0;
            for (int i = o.a; i <= o.b; i++) { cur = max(a[i], cur + a[i]); best = max(best, cur); }
            out.push_back(best);
        }
    }
    return out;
}

Generator spec: n is random from 1 to 20. Values are random from -10 to 10. Up to 30 operations. Each is an update with probability one half (p random from 1 to n, value random from -10 to 10), or a query with l random from 1 to n and r random from l to n. Run 1500 cases.

Show the answer

Use a segment tree whose node stores four values for its range: sum, pre (the best prefix sum), suf (the best suffix sum), and best (the best subarray sum). Two nodes x (left) and y (right) combine as: sum = x.sum + y.sum, pre = max(x.pre, x.sum + y.pre), suf = max(y.suf, y.sum + x.suf), best = max(x.best, y.best, x.suf + y.pre). The combine is associative, which is the rule for a monoid (lesson 04). A point set costs O(log N), and a query costs O(log N). The combine order matters because pre and suf depend on left and right, so the query must combine the left part before the right part. The reference solution is a recursive segment tree and matched the brute force on 1500 random cases. This set does not test a sqrt decomposition for this problem.

Problem 5: Sum of distinct values in a range

You have an array a of N integers, indexed from 1. There are Q queries. Each query gives l and r. Print the sum of the distinct values that appear in a[l] .. a[r]. A value that appears three times counts once.

Input: the first line has N and Q. The second line has the N values. Each of the next Q lines has l r. Limits: N and Q up to 200000, values between 1 and 10^9, the answer fits in a 64-bit integer. Output: one answer per line.

Sample input:

5 3
1 2 1 3 2
1 3
2 5
1 5

Sample output:

3
6
6

The brute force collects the values of each range into a set:

vector<ll> brute5(const vector<ll>& a, const vector<Q5>& qs) {
    vector<ll> out;
    for (auto q : qs) { set<ll> s; for (int i = q.l; i <= q.r; i++) s.insert(a[i]); ll t = 0; for (ll x : s) t += x; out.push_back(t); }
    return out;
}

Generator spec: n is random from 1 to 30. Values are random from 1 to 8, so repeats are common. Up to 30 queries, with l random from 1 to n and r random from l to n. Run 1500 cases.

Show the answer

Sort the queries by their right end r. Walk r from left to right. Keep a Fenwick tree where position i holds a[i] if i is the last position where that value appeared so far, and 0 otherwise. When a[r] arrives, remove its old entry (at its previous last position), add its value at r. For a query with right end r, the answer is the Fenwick sum over [l, r], which counts each distinct value once at its last occurrence. Each step is O(log N), so the total is O((N + Q) log N). The reference solution matched the brute force on 1500 random cases.

Problem 6: Equal pairs in a range

You have an array a of N integers, indexed from 1. There are Q queries. Each query gives l and r. Print the number of pairs of positions (i, j) with l <= i < j <= r and a[i] = a[j].

Input: the first line has N and Q. The second line has the N values. Each of the next Q lines has l r. Limits: N and Q up to 100000, values up to 10^9. Output: one answer per line.

Sample input:

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

Sample output:

4
1
0

The brute force checks every pair in the range:

vector<ll> brute6(const vector<ll>& a, const vector<Q5>& qs) {
    vector<ll> out;
    for (auto q : qs) { ll c = 0; for (int i = q.l; i <= q.r; i++) for (int j = i + 1; j <= q.r; j++) c += a[i] == a[j]; out.push_back(c); }
    return out;
}

Generator spec: n is random from 1 to 40. Values are random from 1 to 6. Up to 40 queries with l random from 1 to n and r random from l to n. Run 1500 cases.

Show the answer

Use Mo's algorithm (lesson 07). Compress the values to indexes. Keep a count cnt[v] for the current window and the current number of equal pairs. Adding a value v at the right adds cnt[v] pairs, then increases cnt[v]. Removing a value v decreases cnt[v] first and then subtracts cnt[v]. Sort the queries by the block of l (block size about N / sqrt(Q)), and alternate the direction of r within each block. The total pointer movement is O(N * sqrt(Q)), which is about 3 * 10^7 steps at the limit. The reference solution matched the brute force on 1500 random cases. For this operation no sparse table or Fenwick tree gives the answer directly, This set does not check a simpler method, so this editorial does not claim one exists.

Problem 7: Smallest covering length

There are N distinct points on a line, given in increasing order as x[1] < ... < x[N]. You want to cover all points with at most K segments. Every segment has the same length L (an integer, L >= 0) and covers the integer interval [s, s + L] for some integer s. A point is covered if it lies in one of the segments. Find the smallest L for which this is possible.

Input: the first line has N and K. The second line has the N positions. Limits: N up to 200000, K from 1 to N, positions between 0 and 10^9. Output: one integer.

Sample input:

6 2
0 1 5 6 11 14

Sample output:

6

If K is 3 on the same points, the answer is 3. The brute force tries every length from 0 upward, and for each length it tries every set of at most K starting points taken from the points. This is correct because a segment can always be moved right so that it starts at its leftmost covered point, which keeps every point it covered:

ll brute7(const vector<ll>& x, int K) {
    int n = x.size();
    for (ll L = 0;; L++) {
        for (int mask = 1; mask < (1 << n); mask++) {
            if (__builtin_popcount(mask) > K) continue;
            bool ok = true;
            for (int p = 0; p < n && ok; p++) {
                bool cov = false;
                for (int s = 0; s < n; s++) if ((mask >> s & 1) && x[s] <= x[p] && x[p] <= x[s] + L) cov = true;
                ok = cov;
            }
            if (ok) return L;
        }
    }
}

Generator spec: n is random from 1 to 7. Choose n distinct integers from 0 to 25 and sort them. K is random from 1 to n. The brute force is exponential, so keep n at 7 or below. Run 1500 cases.

Show the answer

Binary search on L. The check for a given L is greedy: start a segment at the leftmost uncovered point x, cover every point up to x + L, and repeat. Count the segments. The check is monotone in L: if L works, then L + 1 works, because each segment can be the same segment with a longer reach, so the greedy count does not grow. Search L in [0, x[N] - x[1]]. Each check costs O(N), and there are about 30 checks, so the total is O(N log(10^9)). The reference solution matched the brute force on 1500 random cases.

Problem 8: Versions of a multiset

You keep a set of versions of a multiset. Version 0 is the empty multiset. Each operation is one of two kinds.

• I v x: create a new version. It is version v with the value x added. The new version gets the next free number, starting at 1 for the first I operation.
• K w k: print the k-th smallest value (1-based) in version w. The multiset of version w always has at least k values.

Input: the first line has Q. Then Q lines, each in one of the two forms. Limits: Q up to 200000, values between -10^9 and 10^9. Output: one value per line for each K operation.

Sample input:

6
I 0 3
I 0 1
I 1 5
K 3 1
K 3 2
K 2 1

Sample output:

3
5
1

Version 3 is {3, 5}, so the first and second smallest are 3 and 5. Version 2 is {1}.

The brute force copies the multiset for every new version, and a query walks to the k-th element:

vector<ll> brute8(const vector<Op8>& ops) {
    vector<multiset<ll>> ver(1);
    vector<ll> out;
    for (auto o : ops) {
        if (o.type == 1) { auto m = ver[o.from]; m.insert(o.x); ver.push_back(m); }
        else { auto it = ver[o.from].begin(); advance(it, o.k - 1); out.push_back(*it); }
    }
    return out;
}

Generator spec: up to 30 operations. Each operation is an insert with probability one half: from is random from 0 to the current last version number, and x is random from -5 to 5. Otherwise it is a query: pick w at random from the existing versions, and k random from 1 to the size of version w. If version w is empty, skip the operation. Run 1500 cases.

Show the answer

Use a persistent segment tree over the compressed values (lesson 09). Each I operation creates a new root by path copying from the root of version v. That creates about ceil(log2 m) + 1 nodes, where m is the number of distinct values. A K query walks down from the root of version w using the left child count to choose a side, as in the k-th query of lesson 09. Version 0 is the null tree. Each operation costs O(log m). The reference solution matched the brute force on 1500 random cases. Copying the whole multiset for each version, as the brute force does, costs O(N) per version and is too slow at the limit.

Common mistakes

1. Using the tool from the last lesson for every problem. The sample passes, and the first big test is too slow. Name the operation and the limit before you write code.
2. Forgetting that the brute force uses the same indexing as the statement. Problem 2 is 0-based, and the rest are 1-based. A test that shifts all indexes by one still passes on some inputs and fails on others.
3. Trusting one random test. The generator spec uses small values on purpose, so repeats and ties are common. Change the seed and run again.
4. Overflow in the answers of problems 1, 5 and 8. Values up to 10^9 times 200000 items exceed 32-bit range. Use long long.
5. Forgetting the empty case. Problem 3 needs -1 when the total is below S. Problem 7 needs L = 0 when every point is its own segment.

Hands-on exercise

Do this in order.

1. Write the brute force for problem 1 and check it on the sample. Your output must match the sample output.
2. Write your own solution for problem 1 with a difference array. Compare it with the brute force on 1500 random cases from the generator spec. Print the number of mismatches.
3. Choose the tool for problem 6 before you open the editorial. Write one paragraph that names the operation, the limit, and why the other tools do not fit. Then compare it with the editorial.
4. Pick two problems you did not choose a tool for. Solve one with a different tool than the editorial uses. Measure both on a full-size random input from the limits. Report your machine, your compiler and the two times.
5. Pick any problem and change its limit to 1000. Explain in one sentence whether the brute force would now be acceptable.

Prompt for an AI tool to test your solution, with what a good answer looks like:

Here is my solution and the brute force for the problem statement below.
Write a random test generator in C++ that follows this spec: [paste spec].
Then list three inputs that are likely to break my solution, with the reason
for each. Do not change my solution yet.
[paste statement, solution and brute force]

A good answer gives small inputs with ties, empty ranges and boundary values, and each input has a reason. Run each input on the brute force before you trust it. A weak answer gives large random inputs and no reason.

Practice

Each item has a hint. The answer is under "Show the answer".

1. Choose the tool. A problem gives an array of N = 10^6 integers and Q = 10^6 queries, each asking for the sum of a range, with no updates. Name the tool and say what goes wrong with the other tools.

   Hint: the sum is invertible, which matters for a sparse table.

   Show the answer

   Prefix sums. Each query is O(1) after an O(N) build. A sparse table does not work for sums: two overlapping blocks would count the shared elements twice (lesson 02). A segment tree works but costs O(log N) per query, which is slower than needed.

2. Memory check. A persistent tree (problem 8) is used with Q = 2 * 10^5 inserts and m = 2 * 10^5 distinct values. Estimate the bytes with 12 bytes per node.

   Hint: lesson 09 gives the depth and the nodes per insert.

   Show the answer

   The depth for m = 200000 is 18 (lesson 09 measured this). Each insert makes 19 nodes. Total: 2 * 10^5 * 19 = 3,800,000 nodes, about 45.6 MB at 12 bytes each. The lesson 09 measurement with random values created 3,737,856 nodes because a few paths are shorter.

3. Brute force with a limit. Write the brute force for problem 4 and estimate its time at the limit N = Q = 200000.

   Hint: each query scans up to N values.

   Show the answer

   Each query can scan all 200000 values, so the total is up to 200000 * 200000 = 4 * 10^10 steps. Even at an assumed rate of 10^9 simple steps per second (not measured here), that is about 40 seconds, so the brute force is only for checking small inputs.

4. Monotone check. In problem 7, prove that if L covers the points with K segments, then L + 1 also does.

   Hint: a segment of length L starting at s is contained in a segment of length L + 1 starting at s.

   Show the answer

   Replace each segment [s, s + L] by [s, s + L + 1]. Every point covered before is still covered, and the number of segments is unchanged. So L + 1 works with K segments, and the check is monotone in L.

5. Persistence versus copying. In problem 8, a user inserts 200000 values, and each insert is from the latest version. Compare the total memory of copying the whole multiset for every version with the persistent tree.

   Hint: copying stores N values per version, and the persistent tree stores about 19 nodes per insert.

   Show the answer

   Copying stores about 1 + 2 + ... + 200000, which is about 2 * 10^10 values, far too many. The persistent tree stores about 3.8 million nodes (see item 2), so it is about 45 MB. The difference is why persistence is needed for many versions.

Checklist

• Name the operation (sum, min, gcd, count of distinct values, pairs, prefix search) before you name the tool.
• Read the limit first. A tool that is too slow at the limit is the wrong tool, even if it passes the sample.
• Write the brute force before the fast solution, and check it on the sample.
• Generate small random inputs with ties, repeated values and empty or one-element ranges.
• Check the indexing (0-based or 1-based) against the statement, and check the brute force uses the same one.
• Use 64-bit integers when sums can exceed the range of 32-bit integers.
• Run the brute force and your solution on the same input and compare the full output, not only the first line.
• Keep the seed of the random generator, so a failing case can be replayed.

Summary

The set has eight problems. Each one has a different operation, and each limit rules out the naive method and points to one tool. Start by naming the operation and the limit, then write the brute force, then the fast solution, then compare the two on random small inputs.