Round 5: strings and structures

Why this matters when you build with AI

AI tools tend to pick a data structure by habit. Asked "how do I check whether two substrings match", a model often writes a loop that compares characters one by one. That loop is correct on a sample of ten characters. At a string length of 200,000 with 200,000 queries it does far too much work. The mistake is not a typo in the code. It comes from choosing a method without reading the limits.

This round trains one habit: before writing code, count the work the simplest method would do from the limits, then pick the structure that fits the operations. After that, check the AI version against a brute force program on small random inputs. A brute force program solves the task the slow, obvious way, so its answers are easy to trust.

Use this prompt with an AI tool. A good answer names the total work as a number, names one structure, and gives two inputs where a simple method fails.

Limits: n and q are up to 200000 and each query must run in O(log n) or better.
Before any code, answer in this order:
1. The total work of the simplest correct method, as a number.
2. The structure you would use, and one line on why its operations fit the problem.
3. Two inputs where a simple method is too slow, and why.
Then write the code.

Check the answer for two things. First, the operations it names must match the problem: point update, prefix count, substring compare. A generic answer such as "use a map" is not enough. Second, the work number must be computed, not guessed.

Choosing the structure from the constraints

Read the operation first, then the limit. The table gives one structure for each common pattern.

Write one line per problem before any code. Name the operations, the structure, and why the lighter option is not enough. For example: "Fenwick tree: the queries are prefix sums and the updates are point adds, so the Fenwick tree is enough. A segment tree would also work but stores four values per node, which is more code than the task needs."

The techniques in this round

Each technique below has a short definition here. Its full code is in the editorial of the problem that uses it.

Polynomial hashing

A hash turns a string into a number. Let H[i] be the hash of the first i characters, with H[i+1] = H[i] * B + value(c), where B is a base and value(c) maps a letter to a number from 1 to 26. The hash of any substring then comes from two stored values and one power of B, in O(1) time. Two equal strings always have equal hashes. Two different strings can have the same hash. That event is a collision. Using the prime modulus 2^61 - 1 and a random base makes collisions unlikely for a fixed set of inputs, because nobody can predict the base in advance.

An anti-hash case is an input built to make a weak hash collide. The first problem has one, and it breaks a hash that uses natural 64-bit overflow.

Trie

A trie is a tree of characters. Each node is one prefix of some stored word. If each node also stores how many stored words pass through it, the count at the node for p is the number of words that start with p. Inserting "car", "cart" and "cat" makes the nodes c, ca, car, cart and cat. The count at ca is 3. Deleting a word subtracts 1 from each node on its path.

Fenwick tree

A Fenwick tree (also called a binary indexed tree) stores partial sums in an array. Index i holds the sum over the i & -i values ending at i, where i & -i is the lowest set bit of i. A point add and a prefix sum each take O(log n) steps. The loops are for (; i <= n; i += i & -i) for an add and for (; i > 0; i -= i & -i) for a sum.

Segment tree

A segment tree stores one value per node of a binary tree over the array. For a range sum a node stores one number. For the largest piece sum a node stores four numbers: the sum of the range, the best prefix, the best suffix, and the best piece anywhere in the range. Two children combine with three rules: the sum adds, the best prefix is the larger of the left best prefix and the left sum plus the right best prefix, and the best piece is the largest of the two children's best pieces and the left suffix plus the right prefix. For the array -3 4 -1 2 the best piece is 4 -1 2, which sums to 5.

Offline queries with sorting

Offline means all queries are known before any answer is printed. Sort the queries by one coordinate and sweep through the array in that order, keeping a Fenwick tree for the other coordinate. A count in a range [l, r] equals the count up to r minus the count up to l - 1.

KMP prefix function

For a string s, pi[i] is the length of the longest proper prefix of s[0..i] that is also a suffix of it. For abab the values are 0, 0, 1, 2. KMP uses this table to search for a pattern in a text in O(n) total time. A rotation of A is a substring of A + A, so one search finds every rotation.

Worked problem: twin halves

Statement. You get a string s of lowercase letters with length n, where n is at most 2 * 10^5. You get q queries, each with two numbers l and len (0-indexed). Each query has l + 2 * len at most n. For each query print YES if the piece of length len that starts at l equals the piece of length len that starts right after it, and NO otherwise.

Input. The first line is s. The second line is q. Each of the next q lines has l and len.

Method. A direct comparison costs len steps per query. With len near 10^5 and 2 * 10^5 queries that is too slow. A hash gives an O(1) check per query.

The program below stores prefix hashes with the mod 2^61 - 1 arithmetic. mulmod multiplies two numbers below 2^61 using a 128-bit result, then folds the high bits back in, because 2^61 is congruent to 1 modulo 2^61 - 1.

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long u64;
const u64 MOD = (1ULL << 61) - 1;
 
u64 mulmod(u64 a, u64 b) {
    __uint128_t c = (__uint128_t)a * b;
    u64 r = (u64)(c & MOD) + (u64)(c >> 61);
    r = (r & MOD) + (r >> 61);
    if (r >= MOD) r -= MOD;
    return r;
}
 
int main() {
    string s;
    cin >> s;
    int n = s.size();
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    u64 B = rng() % (MOD - 1000) + 500;
    vector<u64> P(n + 1), H(n + 1);
    P[0] = 1;
    for (int i = 0; i < n; i++) {
        P[i + 1] = mulmod(P[i], B);
        H[i + 1] = (mulmod(H[i], B) + (u64)(s[i] - 'a' + 1)) % MOD;
    }
    auto get = [&](int l, int len) {
        return (H[l + len] + MOD - mulmod(H[l], P[len])) % MOD;
    };
    int q;
    cin >> q;
    while (q--) {
        int l, len;
        cin >> l >> len;
        bool same = get(l, len) == get(l + len, len);
        cout << (same ? "YES" : "NO") << "\n";
    }
}

Real output on this input, saved as worked.txt:

abcabcabc
4
0 3
1 2
0 4
2 2

YES
NO
NO
NO

The first query compares abc with abc, so YES. The second compares bc with ab. The third compares abca with bcab. The fourth compares ca with bc. I checked this output against a brute force program that compares the two pieces character by character, and the outputs match.

Anti-hash case. The Thue-Morse string is a string built by repeatedly appending the complement of the current string. Its first 2^11 characters are T, and the next 2^11 characters are the complement of T. The two halves of T followed by its complement differ, so the true answer for l = 0, len = 2048 is NO. I ran a version of the hash that uses natural 64-bit overflow, with an odd random base, on the input T followed by complement(T), with queries 0 2048 and 0 16:

YES
NO

The overflow hash says YES for the first query, which is a false match. The mod 2^61 - 1 hash, and the brute force program, say NO for both queries. The overflow hash does its arithmetic modulo 2^64, a power of two, and that choice is what this input exploits. I ran it with one random base only, so I did not check every base.

Complexity. Setup is O(n) time and memory. Each query is O(1).

The timed set

Give yourself 120 minutes. Read all five statements first, which takes about 5 minutes. Write the one-line structure choice for each problem before any code. Test your code against your own brute force program on random small inputs. Do not read the editorial until the timer ends or you stop on a problem.

Problem 1 is the twin halves problem above. The other four follow.

Problem 2: Stock of words. You get q operations. + w adds the word w. - w removes one copy of w, and w is always present. ? p prints how many current words start with p. Words and query strings are lowercase, and the total length of all of them is at most 2 * 10^5.

Sample input:

6
+ car
+ cart
+ cat
? ca
- cart
? ca

Sample output:

3
2

Problem 3: Peak run. You get n integers a_1 to a_n, where n is at most 2 * 10^5 and each value has absolute value at most 10^9. You get q operations. U i v sets a_i to v. Q l r prints the largest sum of a non-empty piece of consecutive elements inside a_l to a_r.

Sample input:

5
2 -1 3 -4 5
4
Q 1 5
U 4 6
Q 1 5
Q 2 3

Sample output:

5
15
3

Problem 4: Count at most. You get n integers a_1 to a_n, where n is at most 2 * 10^5. You get q queries l r k. Print how many indices i with l at most i at most r have a_i at most k.

Sample input:

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

Sample output:

3
2
1

Problem 5: Rotations. You get two strings A and B of the same length n, where n is at most 2 * 10^5, with lowercase letters only. Rotating A left by k characters means moving its first k characters to the end. Count the values k with 0 at most k below n such that the rotation equals B. Print the count on the first line. Print the smallest such k on the second line, or -1 if there is none.

Sample inputs and outputs:

abcde
cdeab

1
2

abab
abab

2
0

Editorial for problems 2 to 5

Problem 2: a trie with counts

The operations are inserts, deletes and prefix counts, and the total length is 2 * 10^5. The trie answers each in O(length of the string) time. The node reached by p stores the count of words that start with p.

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int cnt;
    array<int, 26> nxt;
};
int main() {
    vector<Node> trie;
    trie.push_back(Node{0, {}});
    trie[0].nxt.fill(0);
    auto newNode = [&]() {
        trie.push_back(Node{0, {}});
        trie.back().nxt.fill(0);
        return (int)trie.size() - 1;
    };
    int q;
    cin >> q;
    while (q--) {
        char op;
        string w;
        cin >> op >> w;
        if (op == '+' || op == '-') {
            int d = op == '+' ? 1 : -1;
            int cur = 0;
            for (char ch : w) {
                int c = ch - 'a';
                if (trie[cur].nxt[c] == 0) {
                    int nn = newNode();
                    trie[cur].nxt[c] = nn;
                }
                cur = trie[cur].nxt[c];
                trie[cur].cnt += d;
            }
        } else {
            int cur = 0;
            bool ok = true;
            for (char ch : w) {
                int c = ch - 'a';
                if (trie[cur].nxt[c] == 0) { ok = false; break; }
                cur = trie[cur].nxt[c];
            }
            cout << (ok ? trie[cur].cnt : 0) << "\n";
        }
    }
}

Output on the sample: 3 then 2. A brute force program that keeps a multiset and counts matching words gives the same output on 400 random inputs with alphabet ab.

Why a lighter option may suffice: a hash map from every prefix to its count costs the length squared for each word. For words of length up to about 20 it is simpler and fast enough. I did not test that variant and I do not claim a timing for it.

Problem 3: a segment tree for the best piece

Each node stores the four numbers from the technique section. The query combines the nodes that cover [l, r]. The empty node uses -10^18 as the sentinel for the best values, not the smallest 64-bit integer, so adding it to a real value cannot overflow.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll NEG = -1000000000000000000LL;
struct Seg {
    ll sum, pre, suf, best;
};
Seg empty_seg() { return Seg{0, NEG, NEG, NEG}; }
Seg join(const Seg& L, const Seg& R) {
    Seg res;
    res.sum = L.sum + R.sum;
    res.pre = max(L.pre, L.sum + R.pre);
    res.suf = max(R.suf, R.sum + L.suf);
    res.best = max({L.best, R.best, L.suf + R.pre});
    return res;
}
int n;
vector<Seg> tree;
vector<ll> a;
void build(int node, int lo, int hi) {
    if (lo == hi) {
        tree[node] = Seg{a[lo], a[lo], a[lo], a[lo]};
        return;
    }
    int mid = (lo + hi) / 2;
    build(2 * node, lo, mid);
    build(2 * node + 1, mid + 1, hi);
    tree[node] = join(tree[2 * node], tree[2 * node + 1]);
}
void update(int node, int lo, int hi, int pos, ll v) {
    if (lo == hi) {
        tree[node] = Seg{v, v, v, v};
        return;
    }
    int mid = (lo + hi) / 2;
    if (pos <= mid) update(2 * node, lo, mid, pos, v);
    else update(2 * node + 1, mid + 1, hi, pos, v);
    tree[node] = join(tree[2 * node], tree[2 * node + 1]);
}
Seg query(int node, int lo, int hi, int l, int r) {
    if (r < lo || hi < l) return empty_seg();
    if (l <= lo && hi <= r) return tree[node];
    int mid = (lo + hi) / 2;
    return join(query(2 * node, lo, mid, l, r), query(2 * node + 1, mid + 1, hi, l, r));
}
int main() {
    cin >> n;
    a.resize(n);
    for (auto& x : a) cin >> x;
    tree.resize(4 * n);
    build(1, 0, n - 1);
    int q;
    cin >> q;
    while (q--) {
        char op;
        cin >> op;
        if (op == 'U') {
            int i;
            ll v;
            cin >> i >> v;
            update(1, 0, n - 1, i - 1, v);
        } else {
            int l, r;
            cin >> l >> r;
            cout << query(1, 0, n - 1, l - 1, r - 1).best << "\n";
        }
    }
}

Output on the sample: 5, 15, 3. The brute force program tries every piece of the query range and gives the same output on 400 random inputs with values between -10 and 10.

Why no lighter structure works: a Fenwick tree stores sums, and a sum cannot give the best piece after a point change. The segment tree is the smallest standard structure for this operation.

Problem 4: offline sweep with a Fenwick tree

Count of a_i <= k on [l, r] equals the count on [1, r] minus the count on [1, l - 1]. Sort the queries by their right end by putting each query at position r with sign +1 and at position l - 1 with sign -1. Sweep the positions from 1 to n and add each value to a Fenwick tree indexed by the rank of the value. The number of distinct values at most k comes from upper_bound.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    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 D = vals.size();
    vector<int> fen(D + 1, 0);
    auto add = [&](int i) {
        for (; i <= D; i += i & -i) fen[i]++;
    };
    auto sum = [&](int i) {
        int s = 0;
        for (; i > 0; i -= i & -i) s += fen[i];
        return s;
    };
    int q;
    cin >> q;
    vector<long long> ans(q, 0);
    vector<int> cut(q);  // number of distinct values <= k
    // events[p] holds (query id, sign) for the prefix ending at position p
    vector<vector<pair<int, int>>> events(n + 1);
    for (int id = 0; id < q; id++) {
        int l, r;
        long long k;
        cin >> l >> r >> k;
        cut[id] = upper_bound(vals.begin(), vals.end(), k) - vals.begin();
        events[r].push_back({id, +1});
        if (l - 1 >= 1) events[l - 1].push_back({id, -1});
    }
    for (int i = 1; i <= n; i++) {
        int rank = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin() + 1;
        add(rank);
        for (auto [id, sign] : events[i]) ans[id] += sign * sum(cut[id]);
    }
    for (int id = 0; id < q; id++) cout << ans[id] << "\n";
}

Output on the sample: 3, 2, 1. The brute force program that loops over the range gives the same output on 400 random inputs. I did not measure the running time at the full limits.

Why no lighter structure works: without the offline sort, a single query would need a 2D structure, which is heavier. Sorting is cheap here because all queries are known in advance.

Problem 5: KMP on A + A

B is a rotation of A by k exactly when B starts at position k of A + A. Find all occurrences of B in A + A, starting positions below n. The loop stops before the last character, so the text is searched only up to position 2n - 2.

#include <bits/stdc++.h>
using namespace std;
int main() {
    string A, B;
    cin >> A >> B;
    int n = A.size();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && B[i] != B[j]) j = pi[j - 1];
        if (B[i] == B[j]) j++;
        pi[i] = j;
    }
    string T = A + A;
    vector<int> shifts;
    int j = 0;
    for (int i = 0; i + 1 < 2 * n; i++) {
        while (j > 0 && T[i] != B[j]) j = pi[j - 1];
        if (T[i] == B[j]) j++;
        if (j == n) {
            shifts.push_back(i - n + 1);
            j = pi[j - 1];
        }
    }
    cout << shifts.size() << "\n";
    cout << (shifts.empty() ? -1 : shifts[0]) << "\n";
}

Output on the two samples: 1 2 for abcde and cdeab, and 2 0 for abab and abab. A brute force program that builds every rotation and compares agrees on 400 random inputs over the alphabet ab.

Why no lighter structure works: a hash scan would also work, but KMP is linear and needs no randomness.

Complexity

Common mistakes

A hash with natural overflow. Using unsigned long long arithmetic without a modulus makes the Thue-Morse test above say YES where the answer is NO. Symptom: a wrong YES on a long periodic string. Fix: use the prime modulus shown in the worked problem.

A segment tree with a zero sentinel. If the empty node has best value 0, an all-negative range answers 0. Symptom: a query on -5 -3 prints 0 instead of -3. Fix: use the very negative sentinel from the editorial.

An off-by-one in the offline events. If you forget that the subtraction happens at l - 1, the counts are too large by everything before l. Symptom: the sample gives a larger count than expected. Fix: check the sample by hand on the first query.

KMP on A only. Searching B inside A misses the rotations that wrap around the end. For the sample abcde and cdeab it prints 0 and -1, but the right output is 1 and 2. Fix: search inside A + A.

Counting the trie node of the full word as zero. The count at the node for the word itself must include that word. Symptom: ? car prints 0 when car is stored. Fix: the count is stored on every node along the path, including the last one.

Hands-on exercise

On your own machine, save the worked problem code as twin.cpp and the input above as worked.txt. Compile with g++ -std=c++17 -O2 -o twin twin.cpp and run ./twin < worked.txt. You should see YES, NO, NO, NO. Then write a brute force program that compares the two halves with a loop and check it on 200 random small inputs. Your timing will differ from anything printed here.

Checklist

1. Write the total work of the simplest method from the limits before coding.
2. Name the operations, then the structure, then why the lighter option is not enough.
3. Use a random base and a prime modulus for hashing.
4. Use a sentinel that cannot overflow when added to real values.
5. Check that query ranges are 1-indexed or 0-indexed in one place only.
6. Test on the sample, then on 200 random small inputs against a brute force program.
7. Search rotations in A + A, not in A.

Practice problems

Practice 1: trie by hand. The operations are + ab, + a, - a, ? a, ? ab. What does each query print?

Show the answer

After + ab and + a, the node for a has count 2. The - a operation lowers it to 1. The query ? a prints 1. The query ? ab prints 1, because only ab starts with ab. Output: 1 then 1.

Practice 2: rotations of a periodic string. Count the rotations of aaa that equal aaa, and give the smallest k.

Show the answer

A + A is aaaaaa. The pattern aaa occurs at positions 0, 1, 2, 3 of the text, and only starts below n = 3 count. So the count is 3 and the smallest k is 0. Output: 3 then 0.

Practice 3: segment tree update. Start with the array -3 4 -1 2. Answer Q 1 4, then U 2 -10, then Q 1 4.

Show the answer

The first query is 5, from the piece 4 -1 2. After the update the array is -3 -10 -1 2. The best piece is the single element 2, so the second query prints 2.

Practice 4: why an equal hash is not proof. Give one reason a hash check can say YES for two different strings, and one way to make the risk smaller.

Show the answer

Two different strings can map to the same number, which is a collision. A random base and a large prime modulus make collisions unlikely for inputs that do not know the base. Using two independent hashes, or comparing the characters directly when the answer matters, removes the risk for a given query.

Summary

Choose the structure from the operations and the limits, not from habit. Hashing answers substring equality in O(1) per query, but it needs a prime modulus and a random base. Tries, segment trees, Fenwick trees and KMP each fit a specific operation pattern. Offline sorting turns a 2D count into a sweep with a Fenwick tree. Check every answer against a brute force program before trusting it.