SyntaxPilot
Courses/Competitive Programming/Lesson 90
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 90 of 90

The road from Pupil to Expert and beyond: practice plan

queued

These are the notes for Competitive Programming episode 90, the last episode of the course. Eighty-nine episodes gave you the tools: a contest template, reading constraints, verdicts, stress testing, prefix sums, two pointers, binary search, greedy, number theory, combinatorics, DP and its optimisations, graphs and trees, segment trees and other range structures, strings, geometry and FFT. Tools do not raise a rating on their own; practice does, and most people practise the wrong way. This episode gives a plan: the rating ladder (where you stand), the practice zone (what to solve), the weekly loop (what to do every week), and the course map (which episodes to study at each stage). Two programs are run live: a small rating planner that uses upper_bound, and one practice session done right on an original problem, where the stress test catches the classic multiset::erase(value) bug. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real. Where a run was slow, the notes say "seconds" instead of quoting a stopwatch: timings depend on the machine.

The real-life hook

Training at the gym. Lifting a weight you already lift easily, a thousand times, keeps you busy but builds no muscle. Trying a weight far beyond you means you fail, learn little and quit. Muscles grow when you lift a bit more than you can, every week: coaches call it progressive overload. Problem solving works the same way. Problems far below your rating are fast and comfortable and leave your rating flat; problems far above it come with editorials you cannot follow yet. Growth happens in the practice zone, roughly 100 to 300 points above your rating: hard enough that you struggle, close enough that the solution teaches you something you will use in the next contest.

The rating ladder

On Codeforces every rated contest changes your rating, and the rating gives a rank (and a colour):

Rank Rating
Newbie below 1200
Pupil 1200 – 1399
Specialist 1400 – 1599
Expert 1600 – 1899
Candidate Master 1900 – 2099
Master 2100 – 2299
International Master 2300 – 2399
Grandmaster 2400 – 2599
International Grandmaster 2600 – 2999
Legendary Grandmaster 3000 and above

AtCoder and CodeChef have their own ladders (AtCoder uses colours by rating, CodeChef uses stars), but the idea is the same. Problems have ratings too: a problem rated 1500 is one that a 1500-rated participant solves about half the time in a contest. So your rating measures what you can solve in a contest, under time pressure: not how many videos you watched, and not how many easy problems you solved.

Rough guide to what each stage solves in a Codeforces Div 2 round: Pupil, A and B reliably; Specialist, A to C; Expert, A to C fast and sometimes D; Candidate Master and above, D and E and Div 1 problems.

Why ratings get stuck, and the practice zone

Practice What it feels like What happens to the rating
many problems far below your rating fast, productive, comfortable flat
problems far above your rating hopeless; the editorial makes no sense flat, and you lose motivation
problems rating + 100 to + 300 hard but within reach grows

Use the problem ratings on the problem set (filter by rating) to pick problems in your zone. When most problems in the zone start to feel comfortable, move the zone up.

A rating planner in C++

from holds where each rank starts and rank holds the names. For a rating r, upper_bound(from.begin(), from.end(), r) finds the first start bigger than r; one step back is the last start ≤ r, which is your rank. That is binary search on a sorted array (episode 11).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<int> from = {0, 1200, 1400, 1600, 1900, 2100, 2300, 2400, 2600, 3000};   // where each rank starts
    vector<string> rank = {"Newbie", "Pupil", "Specialist", "Expert", "Candidate Master", "Master",
                           "International Master", "Grandmaster", "International Grandmaster",
                           "Legendary Grandmaster"};
    int r;
    while (cin >> r) {
        int i = upper_bound(from.begin(), from.end(), r) - from.begin() - 1;   // last start <= r
        cout << r << " " << rank[i];
        if (i + 1 < (int)from.size()) cout << " · " << from[i + 1] - r << " to the next rank";
        cout << " · practise " << r + 100 << "-" << r + 300 << "\n";
    }
}

Input (one rating per line):

1150
1350
1600
2450
1150 Newbie · 50 to the next rank · practise 1250-1450
1350 Pupil · 50 to the next rank · practise 1450-1650
1600 Expert · 300 to the next rank · practise 1700-1900
2450 Grandmaster · 150 to the next rank · practise 2550-2750

The edges are right too: 1199 is a Newbie and 1200 a Pupil, 1599 a Specialist and 1600 an Expert, 3000 a Legendary Grandmaster with no next rank (checked on every boundary).

The weekly loop

Four steps, every week:

  1. Contest. One or two rated contests a week, for the full time, with no editorials. If the time does not suit you, do a virtual contest: an old round with the official timer, as if it were live (Codeforces lets you take part virtually in past rounds).
  2. Upsolve. Upsolving means solving, after the contest, the problems you could not solve during it. Do at least the next one or two problems after your last solve. This is where most of the rating comes from: they are, by definition, in your practice zone.
  3. One topic. One topic a week from the course map below: watch the episode, then solve about five problems on that topic in your practice zone.
  4. Mistake log. One line per lost problem: date, problem, a short tag, and the idea you missed in one sentence. Read it before every contest. After a month the tags tell you what to study next.

The stuck rule. When you are stuck for 30 to 45 minutes, read one hint (the first paragraph of the editorial, or a hint from a friend), not the whole solution, and try again. After reading an editorial, close it and write the code yourself from memory. If you cannot, you have not understood it yet; read it again.

The submit rule. Before you submit a problem with a fast idea: write the brute force, stress test (episode 5), think about the edge cases (n = 1, all equal, the largest values), and check the complexity against the constraints (episode 3). The live session below shows why.

The course map by stage

Stage Episodes Topics Typical problems
To Pupil (1200) 1-16 template, constraints, verdicts, stress testing, strategy, prefix sums, difference arrays, coordinate compression, two pointers, binary search on the answer, ternary search, sorting, greedy, constructive, ad hoc Div 2 A and B
To Specialist (1400) 17-31 bit tricks, meet in the middle, GCD, sieve, modular arithmetic, inverses, nCr, inclusion-exclusion, CRT, totient, expected value, matrix power, game theory Div 2 B and C
To Expert (1600) 32-40, 45-54 DP states, knapsack, strings DP, interval, bitmask, digit, tree DP, SOS, expected-value DP; BFS/DFS, Dijkstra, DSU, MST, topological order, bridges, SCC and 2-SAT, trees, LCA, Euler tour Div 2 C and D
To Candidate Master (1900) 41-44, 61-78 DP optimisations (monotonic queue, convex hull trick, divide and conquer, Knuth), lazy segment trees, Fenwick tricks, sparse table, sqrt decomposition, Mo's, persistent trees, ordered set, treap, monotonic stack, hashing, KMP, Z, Manacher, trie, Aho-Corasick, suffix array and automaton Div 2 D and E, Div 1 A to C
Beyond 55-60, 79-86 heavy-light and centroid decomposition, functional graphs, flows, matching, min-cost flow, geometry, FFT and NTT, interactive problems, randomisation, bitsets Div 1

Do not study the map in a straight line for months. One topic a week from your stage, and the rest of the time, the loop. Learn the "Beyond" topics when you meet them in problems in your zone, not before. Episodes 87 to 89 (the contest walkthroughs) are worth rewatching at every stage.

A live practice session: Calm Playlist

A problem at about 1500, written for this course.

  • n ≤ 2·10^5 songs in order, each with a mood a[i] (an integer), and a number k ≥ 0.
  • A calm block is a run of neighbouring songs whose highest mood minus lowest mood is at most k.
  • Print the length of the longest calm block.

Sample. 7 2 / 4 6 5 3 5 5 7 → 4 (the block 5 3 5 5: highest 5, lowest 3).

Constraints first. n = 2·10^5, so O(n²) is about 2·10^10 operations: too slow. We need about O(n log n) or O(n).

The brute force (the referee)

Every start; grow to the right with a running max and min; stop as soon as the block is too wild (a longer block would be at least as wild).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    int best = 0;
    for (int l = 0; l < n; l++) {                   // every start
        int mx = a[l], mn = a[l];
        for (int r = l; r < n; r++) {
            mx = max(mx, a[r]);
            mn = min(mn, a[r]);
            if (mx - mn > k) break;                 // too wild: longer is worse
            best = max(best, r - l + 1);
        }
    }
    cout << best << "\n";
}
4

With slowly drifting moods the calm blocks are long, and the brute force walks each of them from every start. At half the limit:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    mt19937 gen(90);
    int n = 100000, k = 30000;                // half the limit
    vector<int> a(n);
    for (int i = 0; i < n; i++) a[i] = i + gen() % 1000;   // the mood drifts up slowly
    int best = 0;
    for (int l = 0; l < n; l++) {                   // every start
        int mx = a[l], mn = a[l];
        for (int r = l; r < n; r++) {
            mx = max(mx, a[r]);
            mn = min(mn, a[r]);
            if (mx - mn > k) break;                 // too wild: longer is worse
            best = max(best, r - l + 1);
        }
    }
    cout << best << "\n";
}
29194

Seconds at n = 10^5. Too slow.

The idea: two pointers and a multiset

If a block is calm, every smaller block inside it is calm too. So as the right end r moves right, the best left end l never moves back: two pointers (episode 10). A multiset holds the moods in the window [l, r]; its smallest element is *s.begin() and its largest *s.rbegin(). Move r, insert a[r]; while the window is too wild, remove a[l] and move l. O(n log n).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    multiset<int> s;                                // moods in the window [l, r]
    int best = 0, l = 0;
    for (int r = 0; r < n; r++) {
        s.insert(a[r]);
        while (*s.rbegin() - *s.begin() > k)        // max - min too big: shrink from the left
            s.erase(a[l++]);
        best = max(best, r - l + 1);
    }
    cout << best << "\n";
}
4

The sample passes. A rushed submit would happen here. Stress test first, with moods from only four values so that repeats are everywhere:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int brute(int n, int k, vector<int>& a) {
    int best = 0;
    for (int l = 0; l < n; l++) {                   // every start
        int mx = a[l], mn = a[l];
        for (int r = l; r < n; r++) {
            mx = max(mx, a[r]);
            mn = min(mn, a[r]);
            if (mx - mn > k) break;                 // too wild: longer is worse
            best = max(best, r - l + 1);
        }
    }
    return best;
}

int fast(int n, int k, vector<int>& a) {
    multiset<int> s;                                // moods in the window [l, r]
    int best = 0, l = 0;
    for (int r = 0; r < n; r++) {
        s.insert(a[r]);
        while (*s.rbegin() - *s.begin() > k)        // max - min too big: shrink from the left
            s.erase(a[l++]);
        best = max(best, r - l + 1);
    }
    return best;
}

int main() {
    mt19937 gen(90);
    for (int it = 1; it <= 1000; it++) {
        int n = gen() % 8 + 1, k = gen() % 3;
        vector<int> a(n);
        for (int& x : a) x = gen() % 4 + 4;           // moods 4..7: lots of repeats
        if (brute(n, k, a) != fast(n, k, a)) {
            cout << "differs on test " << it << ": n = " << n << ", k = " << k << ", moods";
            for (int x : a) cout << " " << x;
            cout << "\nbrute " << brute(n, k, a) << ", fast " << fast(n, k, a);
            return 0;
        }
    }
    cout << "all 1000 tests agree";
}
differs on test 5: n = 8, k = 1, moods 4 7 4 4 6 5 4 6
brute 2, fast 4

The smallest failing case of this kind, by hand: 4 0 / 4 4 5 5 (k = 0: only equal moods may share a block).

3

But no calm block is longer than 2. When the 5 arrives the window 4 4 5 is too wild, so we remove a[0] = 4. s.erase(4) removes every 4 in the multiset, including the 4 at position 1 that is still inside the window. The multiset now holds only 5, so the window [1, 2] looks calm, and when the second 5 arrives the window [1, 3] still looks calm: length 3.

The fix: erase one copy

s.find(value) returns an iterator to one copy; erasing that iterator removes exactly one element.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    multiset<int> s;                                // moods in the window [l, r]
    int best = 0, l = 0;
    for (int r = 0; r < n; r++) {
        s.insert(a[r]);
        while (*s.rbegin() - *s.begin() > k)        // max - min too big: shrink from the left
            s.erase(s.find(a[l++]));               // remove ONE copy
        best = max(best, r - l + 1);
    }
    cout << best << "\n";
}
2
4

The stress test again:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int brute(int n, int k, vector<int>& a) {
    int best = 0;
    for (int l = 0; l < n; l++) {                   // every start
        int mx = a[l], mn = a[l];
        for (int r = l; r < n; r++) {
            mx = max(mx, a[r]);
            mn = min(mn, a[r]);
            if (mx - mn > k) break;                 // too wild: longer is worse
            best = max(best, r - l + 1);
        }
    }
    return best;
}

int fast(int n, int k, vector<int>& a) {
    multiset<int> s;                                // moods in the window [l, r]
    int best = 0, l = 0;
    for (int r = 0; r < n; r++) {
        s.insert(a[r]);
        while (*s.rbegin() - *s.begin() > k)        // max - min too big: shrink from the left
            s.erase(s.find(a[l++]));               // remove ONE copy
        best = max(best, r - l + 1);
    }
    return best;
}

int main() {
    mt19937 gen(90);
    for (int it = 1; it <= 1000; it++) {
        int n = gen() % 8 + 1, k = gen() % 3;
        vector<int> a(n);
        for (int& x : a) x = gen() % 4 + 4;           // moods 4..7: lots of repeats
        if (brute(n, k, a) != fast(n, k, a)) {
            cout << "differs on test " << it << ": n = " << n << ", k = " << k << ", moods";
            for (int x : a) cout << " " << x;
            cout << "\nbrute " << brute(n, k, a) << ", fast " << fast(n, k, a);
            return 0;
        }
    }
    cout << "all 1000 tests agree";
}
all 1000 tests agree

And the full size, 2·10^5 drifting songs:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    mt19937 gen(90);
    int n = 200000, k = 30000;                // the largest test
    vector<int> a(n);
    for (int i = 0; i < n; i++) a[i] = i + gen() % 1000;   // the mood drifts up slowly
    multiset<int> s;                                // moods in the window [l, r]
    int best = 0, l = 0;
    for (int r = 0; r < n; r++) {
        s.insert(a[r]);
        while (*s.rbegin() - *s.begin() > k)        // max - min too big: shrink from the left
            s.erase(s.find(a[l++]));               // remove ONE copy
        best = max(best, r - l + 1);
    }
    cout << best << "\n";
}
29213

Instant. Now submit, and add one line to the mistake log: multiset erase by value removes every copy; use erase(find(value)).

Complexity vs the constraints

Solution Time Memory At n = 2·10^5
Calm Playlist: brute force, every start O(n²) worst case O(n) TLE when calm blocks are long
two pointers + multiset O(n log n) O(n) Accepted
two pointers + two monotonic deques (practice 2) O(n) O(n) Accepted
planner: upper_bound over the rank starts O(log R) per rating O(R) instant

Common mistakes (practice and code)

Mistake What you see Why Fix
solving 100 easy problems a week a flat rating nothing new to learn practise at rating + 100 to + 300
reading the editorial after 5 minutes no ideas of your own in contests the struggle is the training 30-45 minutes, then one hint
never upsolving the same wall every round you skip the problems that teach upsolve 1-2 past your last solve
submitting because the sample passed WA on test 2 samples miss ties and edge cases brute force + stress test first
quitting after one bad contest no progress at all ratings swing by about ±100 from round to round judge the trend over months
s.erase(value) on a multiset 3 instead of 2 on 4 4 5 5, k = 0 erase by value removes every copy s.erase(s.find(value))

Mini project: a mistake log analyser

Keep the log as a text file, one line per lost problem: date | problem | tag | the idea in one sentence. This program counts the tags, most frequent first, and shows the latest idea for each: the top tag is next week's topic.

#include <bits/stdc++.h>
using namespace std;

// Mistake log analyser. Each line: date | problem | tag | the idea in one sentence
// Prints how often each tag appears (most frequent first): that is next week's topic.
int main() {
    map<string, int> cnt;
    map<string, string> last;
    string line;
    int total = 0;
    while (getline(cin, line)) {
        vector<string> f;
        stringstream ss(line);
        string part;
        while (getline(ss, part, '|')) {
            size_t a = part.find_first_not_of(' '), b = part.find_last_not_of(' ');
            f.push_back(a == string::npos ? "" : part.substr(a, b - a + 1));
        }
        if (f.size() < 4) continue;                 // skip blank or broken lines
        cnt[f[2]]++;
        last[f[2]] = f[3];
        total++;
    }
    vector<pair<int, string>> v;
    for (auto& [tag, c] : cnt) v.push_back({-c, tag});
    sort(v.begin(), v.end());
    cout << total << " lost problems\n";
    for (auto& [c, tag] : v) cout << setw(3) << -c << "  " << tag << "  (last: " << last[tag] << ")\n";
}

The log:

2026-11-01 | round 1 C | ties | two equal maxima: one side >=, the other >
2026-11-03 | round 2 B | overflow | n * n with n = 2e5 needs long long
2026-11-04 | virtual D | multiset | erase(value) removes every copy: erase(find(value))
2026-11-08 | round 3 C | ties | sort by (value, index) so equal values have an order
2026-11-09 | upsolve D | binary search | lo = mid needs mid rounded up
2026-11-10 | round 4 B | overflow | the sum of 2e5 values up to 1e9 is 2e14
2026-11-11 | round 4 C | ties | strictly greater means sum(r - 1), not sum(r)
7 lost problems
  3  ties  (last: strictly greater means sum(r - 1), not sum(r))
  2  overflow  (last: the sum of 2e5 values up to 1e9 is 2e14)
  1  binary search  (last: lo = mid needs mid rounded up)
  1  multiset  (last: erase(value) removes every copy: erase(find(value)))

Ties were lost three times: next week, rewatch episode 89 and solve five problems with equal values.

Practice

1. The trend. Read your rating after every rated contest (oldest first) and print the number of contests, the current and best rating, and the average change over the last five contests.

Solution
#include <bits/stdc++.h>
using namespace std;

// Rating history -> the trend. One rated contest per number, oldest first.
int main() {
    vector<int> r;
    int x;
    while (cin >> x) r.push_back(x);
    int n = r.size();
    if (n < 2) { cout << "need at least 2 contests\n"; return 0; }
    int best = *max_element(r.begin(), r.end());
    int k = min(n - 1, 5);                          // the last 5 changes
    double avg = double(r[n - 1] - r[n - 1 - k]) / k;
    cout << "contests " << n << ", now " << r[n - 1] << ", best " << best << "\n";
    cout << "last " << k << " changes: " << fixed << setprecision(1) << avg << " per contest\n";
    cout << (avg > 0 ? "trend: up, keep the loop going\n" : "trend: flat or down, check the practice zone and the log\n");
}

Input 1180 1215 1160 1240 1290 1265 1330 1310 1372:

contests 9, now 1372, best 1372
last 5 changes: 26.4 per contest
trend: up, keep the loop going

The average over the last five changes is (1372 − 1240) / 5 = 26.4: one bad contest (1330 → 1310) does not change the trend.

2. Calm Playlist in O(n). Replace the multiset with two monotonic deques: one keeps indices with decreasing moods (its front is the window's max), the other increasing moods (its front is the min). When l moves past a front index, pop it.

Solution
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    deque<int> mx, mn;                              // indices: moods decreasing in mx, increasing in mn
    int best = 0, l = 0;
    for (int r = 0; r < n; r++) {
        while (!mx.empty() && a[mx.back()] <= a[r]) mx.pop_back();
        mx.push_back(r);
        while (!mn.empty() && a[mn.back()] >= a[r]) mn.pop_back();
        mn.push_back(r);
        while (a[mx.front()] - a[mn.front()] > k) { // too wild: shrink from the left
            l++;
            if (mx.front() < l) mx.pop_front();
            if (mn.front() < l) mn.pop_front();
        }
        best = max(best, r - l + 1);
    }
    cout << best << "\n";
}
4
2

Each index enters and leaves each deque once: O(n). Deques of indices never have the "erase every copy" problem, because equal moods at different positions are different indices.

3. Where is the block? Print the first and last song of the longest calm block (the leftmost one if there are several).

Solution

Record l whenever the window becomes strictly longer than the best so far; a strict comparison keeps the leftmost block.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    multiset<int> s;
    int best = 0, from = 0, l = 0;
    for (int r = 0; r < n; r++) {
        s.insert(a[r]);
        while (*s.rbegin() - *s.begin() > k) s.erase(s.find(a[l++]));
        if (r - l + 1 > best) { best = r - l + 1; from = l; }   // strictly longer: keeps the LEFTMOST
    }
    cout << "longest calm block: songs " << from + 1 << " to " << from + best << " (length " << best << ")\n";
}
longest calm block: songs 3 to 6 (length 4)

4. The upsolve picker. Given your rating and a list of problems (name, rating, solved or not), print the unsolved problems in your practice zone, easiest first.

Solution
#include <bits/stdc++.h>
using namespace std;

// Upsolve picker. Input: your rating, then lines "name rating solved(0/1)".
// Prints the unsolved problems in your practice zone [r + 100, r + 300], easiest first.
int main() {
    int r;
    cin >> r;
    vector<pair<int, string>> pick;
    string name;
    int rating, solved;
    while (cin >> name >> rating >> solved)
        if (!solved && rating >= r + 100 && rating <= r + 300) pick.push_back({rating, name});
    sort(pick.begin(), pick.end());
    cout << pick.size() << " problems in your zone " << r + 100 << "-" << r + 300 << ":\n";
    for (auto& [x, nm] : pick) cout << "  " << nm << " (" << x << ")\n";
}

Input:

1350
round1-A 800 1
round1-B 1200 1
round1-C 1500 0
round1-D 1900 0
round2-B 1300 0
round2-C 1600 0
round3-C 1450 1
round3-D 1650 0
3 problems in your zone 1450-1650:
  round1-C (1500)
  round2-C (1600)
  round3-D (1650)

5. A stress-test harness you keep. Write a shell script that compiles a generator, a brute force and a fast solution, then compares them on 200 random tests and stops at the first difference.

Solution

The generator takes a seed, so every failing test can be reproduced:

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char** argv) {                   // ./gen SEED  -> one small random test
    mt19937 gen(atoi(argv[1]));
    int n = gen() % 8 + 1, k = gen() % 3;
    cout << n << " " << k << "\n";
    for (int i = 0; i < n; i++) cout << gen() % 4 + 4 << " \n"[i == n - 1];
}
#!/bin/sh
# stress.sh: compile once, then compare brute and fast on random tests until they differ
g++ -O2 -std=c++17 gen.cpp -o gen && g++ -O2 -std=c++17 brute.cpp -o brute && g++ -O2 -std=c++17 fast.cpp -o fast || exit 1
for i in $(seq 1 200); do
    ./gen $i > in.txt
    ./brute < in.txt > want.txt
    ./fast < in.txt > got.txt
    if ! cmp -s want.txt got.txt; then
        echo "differs on seed $i"; cat in.txt; echo "brute: $(cat want.txt), fast: $(cat got.txt)"; exit 1
    fi
done
echo "all 200 tests agree"

With fast.cpp = the multiset version that erases by value, and brute.cpp = the brute force:

differs on seed 1
6 2
4 4 7 5 7 5
brute: 4, fast: 5

With the fixed version:

all 200 tests agree

(On the failing test the window 4 4 7 is too wild, erase(4) removes both 4s, and the fast solution reports 5 where the longest calm block is 4.)

Quick quiz

multiset<int> s = {5, 5, 7};
s.erase(5);
cout << s.size();

A) 0 · B) 1 · C) 2 · D) 3

Answer: B, 1. erase(value) removes every 5, leaving {7}. To remove one copy: s.erase(s.find(5)) (check first that find did not return s.end()).

Interview questions

  1. How would you prepare for coding contests in three months? Contests every week, upsolving, one topic a week at the edge of my level, a mistake log, and stress testing before submitting; judge progress by the rating trend.
  2. What is upsolving and why does it matter? Solving, after a contest, the problems you could not solve during it. They are exactly at the edge of your level, so they teach the most.
  3. How do you choose practice problems? By problem rating, about 100 to 300 above my own rating, and by the topics my mistake log says I lose most often.
  4. What does upper_bound return, and how do you find the last element ≤ x? An iterator to the first element strictly greater than x; one position before it is the last element ≤ x (if it is not the first position).
  5. What is the difference between s.erase(x) and s.erase(s.find(x)) on a multiset? The first removes all copies of x and returns how many it removed; the second removes one element (and must not be called with end()).
  6. When do two pointers work? When the property is monotonic: if a window is good, every window inside it is good (or the reverse), so the left pointer never has to move back.
  7. Why stress test even when the idea is proven? Proofs cover the idea, not the code: off-by-one errors, ties, overflow and library surprises (like erase) only show up when the code runs on many inputs.

Glossary

Term Meaning
rating A number estimating your contest strength; it changes after every rated contest
rank The title for a rating band (Pupil, Specialist, Expert, ...)
problem rating The rating of a participant who solves that problem about half the time in a contest
practice zone Problems about 100 to 300 points above your rating
progressive overload Training principle: increase the difficulty a little, steadily
virtual contest Taking part in a past contest later, with the official timer, as if it were live
upsolving Solving the problems of a contest after it ends, the ones you could not solve during it
editorial The official explanation of a contest's solutions, published after it ends
hint One idea from the solution, not the whole solution
mistake log A file with one line per lost problem: date, problem, tag, the missed idea
Div 1 / Div 2 The harder and easier divisions of a Codeforces round
upper_bound Returns the first position whose value is strictly greater than x, in a sorted range
two pointers Two indices moving in one direction over an array, keeping a window with a monotonic property
window The current block [l, r] between the two pointers
multiset A sorted container (a balanced tree) that allows repeated values; insert, erase and find in O(log n)
erase(value) On a multiset: removes every copy of the value
erase(iterator) Removes exactly the one element the iterator points to
monotonic deque A double-ended queue whose values stay sorted; gives a sliding-window max or min in O(1)
stress test Comparing a fast solution with a slow, trusted one on many random small inputs
referee / brute force The slow, obviously correct solution used to check the fast one
generator A small program that prints one random test, usually from a seed
trend The direction of the rating over many contests, not one round

Summary

  • Your rating measures what you solve in a contest. Know your rank and your practice zone: rating + 100 to + 300.
  • Every week: a contest (live or virtual), upsolving of the next one or two problems, one topic from the course map with five problems, and the mistake log.
  • When stuck for 30-45 minutes, take one hint; after an editorial, write the code yourself.
  • Brute force and stress test before you submit: today the sample passed and multiset::erase(value) still removed every copy.
  • Judge progress by the trend over months, not by one round.
  • That completes the Competitive Programming course: ninety episodes, from what a verdict is to Div 1 rounds. Keep practising with the DSA and coding questions series on SyntaxPilot.

Solutions in C++, Java and Python

Calm Playlist

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    multiset<int> s;                                // moods in the window [l, r]
    int best = 0, l = 0;
    for (int r = 0; r < n; r++) {
        s.insert(a[r]);
        while (*s.rbegin() - *s.begin() > k)        // max - min too big: shrink from the left
            s.erase(s.find(a[l++]));               // remove ONE copy
        best = max(best, r - l + 1);
    }
    cout << best << "\n";
}

Java (a TreeMap from mood to count plays the multiset; removing one copy means decrementing the count)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        st.nextToken(); int n = (int) st.nval;
        st.nextToken(); int k = (int) st.nval;
        int[] a = new int[n];
        for (int i = 0; i < n; i++) { st.nextToken(); a[i] = (int) st.nval; }
        TreeMap<Integer, Integer> s = new TreeMap<>();            // mood -> how many times in the window
        int best = 0, l = 0;
        for (int r = 0; r < n; r++) {
            s.merge(a[r], 1, Integer::sum);
            while (s.lastKey() - s.firstKey() > k) {              // too wild: shrink from the left
                if (s.merge(a[l], -1, Integer::sum) == 0) s.remove(a[l]);   // remove ONE copy
                l++;
            }
            best = Math.max(best, r - l + 1);
        }
        System.out.println(best);
    }
}

Python (two monotonic deques, O(n))

import sys
from collections import deque

def main():
    data = sys.stdin.buffer.read().split()
    n, k = int(data[0]), int(data[1])
    a = list(map(int, data[2:2 + n]))
    mx, mn = deque(), deque()                # indices: moods decreasing in mx, increasing in mn
    best = l = 0
    for r in range(n):
        while mx and a[mx[-1]] <= a[r]:
            mx.pop()
        mx.append(r)
        while mn and a[mn[-1]] >= a[r]:
            mn.pop()
        mn.append(r)
        while a[mx[0]] - a[mn[0]] > k:       # too wild: shrink from the left
            l += 1
            if mx[0] < l:
                mx.popleft()
            if mn[0] < l:
                mn.popleft()
        best = max(best, r - l + 1)
    print(best)

main()

All three print 4 on the sample and 2 on 4 4 5 5 with k = 0, and they agreed with the brute force on 150 random playlists.

The rating planner

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<int> from = {0, 1200, 1400, 1600, 1900, 2100, 2300, 2400, 2600, 3000};   // where each rank starts
    vector<string> rank = {"Newbie", "Pupil", "Specialist", "Expert", "Candidate Master", "Master",
                           "International Master", "Grandmaster", "International Grandmaster",
                           "Legendary Grandmaster"};
    int r;
    while (cin >> r) {
        int i = upper_bound(from.begin(), from.end(), r) - from.begin() - 1;   // last start <= r
        cout << r << " " << rank[i];
        if (i + 1 < (int)from.size()) cout << " · " << from[i + 1] - r << " to the next rank";
        cout << " · practise " << r + 100 << "-" << r + 300 << "\n";
    }
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] from = {0, 1200, 1400, 1600, 1900, 2100, 2300, 2400, 2600, 3000};
        String[] rank = {"Newbie", "Pupil", "Specialist", "Expert", "Candidate Master", "Master",
                         "International Master", "Grandmaster", "International Grandmaster", "Legendary Grandmaster"};
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int r = sc.nextInt();
            int i = 0;
            while (i + 1 < from.length && from[i + 1] <= r) i++;     // last start <= r (10 ranks: a scan is fine)
            StringBuilder sb = new StringBuilder(r + " " + rank[i]);
            if (i + 1 < from.length) sb.append(" · ").append(from[i + 1] - r).append(" to the next rank");
            sb.append(" · practise ").append(r + 100).append("-").append(r + 300);
            System.out.println(sb);
        }
    }
}

Python

import sys
from bisect import bisect_right

FROM = [0, 1200, 1400, 1600, 1900, 2100, 2300, 2400, 2600, 3000]
RANK = ["Newbie", "Pupil", "Specialist", "Expert", "Candidate Master", "Master",
        "International Master", "Grandmaster", "International Grandmaster", "Legendary Grandmaster"]

for tok in sys.stdin.read().split():
    r = int(tok)
    i = bisect_right(FROM, r) - 1            # last start <= r
    line = f"{r} {RANK[i]}"
    if i + 1 < len(FROM):
        line += f" · {FROM[i + 1] - r} to the next rank"
    print(line + f" · practise {r + 100}-{r + 300}")

All three print the same lines for every rank boundary from 0 to 3500.