Complexity Budget Practice Test for Competitive Programmers
A timed 45-minute check: match constraints to the complexity that passes in one second, spot int overflow, and solve a query problem within budget in C++.
- Course: Competitive Programming study plan
- Module: Fast I/O and complexity budgets
- Kind: Checkpoint — cleared at 70%
- Reading time: 45 min
- Runtime: Clang 18 · C++20
Checkpoint — Fast I/O and complexity budgets is the checkpoint that closes the Fast I/O and complexity budgets module: a graded quiz and whole-program exercises, passed at 70%.
Instructions
The first timed checkpoint of the track. Like a contest round, it has a clock: 45 minutes from when you start it.
What it covers. Turning a constraint into a complexity budget at about 10⁸ operations per second, the contest template's fast-I/O lines, and long long against overflow.
How it works. Eleven questions and one program. Clear 70% of the questions and get the program accepted — its hidden cases are at the limits, so an O(n · q) scan runs out of time where an O((n + q) log n) one passes.
Before you start, make sure you can say from memory:
- the slowest complexity that fits n ≤ 20, 400, 5000, 10⁶ and 10¹⁸;
- what
1LL * a * bfixes; - why
endlis slow and whatcin.tie(nullptr)removes.
Common questions
How long is this checkpoint?
Forty-five minutes from the moment you start its timer. Answers sent after the clock runs out do not clear the checkpoint, the way a contest stops accepting submissions at the end.
Exercise
How many are at most x
Read n values and then answer q queries: for each query value x, print how many of the values are ≤ x.
Constraints: 1 ≤ n, q ≤ 2·10⁵, 0 ≤ aᵢ, x ≤ 10⁹.
Input: n q, then the n values, then q lines with one x each. Output: q lines, one answer each.
5 3
4 1 7 4 2
4
0
10prints
4
0
5Scanning all n values per query is O(n · q) = 4·10¹⁰ at the limits — budget first.
In this module: Fast I/O and complexity budgets
← The contest template and complexity budgets · Prefix sums and difference arrays →