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:
- 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).
- 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.
- 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.
- 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
- 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.
- 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.
- 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.
- What does
upper_boundreturn, 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). - What is the difference between
s.erase(x)ands.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 withend()). - 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.
- 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.