These are the notes for Competitive Programming episode 3. A solution that is correct but too slow gets Time Limit Exceeded, which is just as wrong as a wrong answer. Here you learn to count operations, the rule of thumb of about 10^8 simple steps per second, Big-O in plain words, and the constraints table that tells you which algorithm can pass before you write any code. The running example is an original problem, Ticket Pairs, solved first by brute force (timed live until it times out) and then in O(n log n). Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler). Timings are from the recording machine and vary per run; the growth pattern does not.
The problem: Ticket Pairs
Problem C · Ticket Pairs (written for this course). A college fest raffle has
ntickets with numbersa[1..n], and a lucky sumS. Count the pairsi < jwitha[i] + a[j] = S.Constraints:
1 ≤ n ≤ 2·10^5,1 ≤ a[i], S ≤ 10^9. Time limit: 1 second.
| Sample input | Sample output |
|---|---|
5 71 6 3 4 3 |
3 |
The pairs are 1+6, 3+4 and 4+3 (the two 3s are different tickets, so both count).
Brute force: try every pair
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
ll S;
cin >> n >> S;
vector<ll> a(n);
for (auto &x : a) cin >> x;
ll pairs = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (a[i] + a[j] == S) pairs++;
cout << pairs << '\n';
return 0;
}
Sample: prints 3. Correct. But is it fast enough for n = 200,000?
Timing it
The video's timing version generates n random tickets itself (with the random generator mt19937, seeded with 42 so every run makes the same tickets) and times only the double loop:
int n;
cin >> n;
mt19937 rng(42);
vector<ll> a(n);
for (auto &x : a) x = rng() % 1000000 + 1;
ll S = 1000000;
auto start = chrono::steady_clock::now();
ll pairs = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (a[i] + a[j] == S) pairs++;
auto end = chrono::steady_clock::now();
cout << "pairs = " << pairs << '\n';
cout << "time: " << (end - start) / 1ms << " ms\n";
| n | Output (one run) |
|---|---|
| 50,000 | pairs = 1293, time: 895 ms |
| 100,000 | pairs = 5152, time: 3561 ms (2× n → about 4× time) |
| 200,000 | Time Limit Exceeded (the SyntaxPilot compiler stops at 8 s; a judge at 1 s) |
Counting operations
The double loop checks n(n−1)/2 pairs. For n = 2·10^5 that is about 2·10^10 checks.
Rule of thumb: a judge does roughly 10^8 simple operations per second. Very simple, cache-friendly loops can reach ~10^9 (the compiler can even use vector instructions, as in our timing), but plan with 10^8 and you will rarely be surprised.
2·10^10 / 10^8 = 200 seconds, against a limit of 1 second. Nothing rescues that: not fast I/O, not -O2, not clever micro-optimisation.
Big-O in plain words
Big-O describes how the amount of work grows as n grows, ignoring constant factors.
| Real life | Big-O | Double n → work |
|---|---|---|
| Everyone at a party shakes hands with everyone (10 guests: 45; 1000 guests: ~500,000) | O(n²) | × 4 |
| Everyone signs the guest register once | O(n) | × 2 |
| Finding a name in a sorted guest list by halving | O(log n) | + 1 step |
| Sorting the guest list | O(n log n) | a bit more than × 2 |
The constraints table (time limit about 1 second)
| Max n | Complexity that fits | Typical technique |
|---|---|---|
| ≤ 10–11 | O(n!) | try every order (permutations) |
| ≤ 20–25 | O(2^n · n) | try every subset (bitmasks) |
| ≤ 100 | O(n^4) | four nested loops |
| ≤ 500 | O(n^3) | triple loop, Floyd–Warshall |
| ≤ 5000 | O(n^2) | double loop, 2D DP |
| ≤ 2·10^5 (up to ~10^6) | O(n log n) or O(n √n) | sorting, map/set, binary search, segment tree |
| ≤ 10^7 – 10^8 | O(n) | one pass, prefix sums, two pointers |
| ≤ 10^18 | O(log n) or O(1) | maths, binary search on the answer, fast power |
Problem setters choose n on purpose to let exactly one of these through. The constraint is a hint about the intended solution.
Inventing the fast solution: the register
n ≤ 2·10^5 means we need about O(n log n). Turn the question around: when ticket x arrives, its partner must be exactly S − x. So keep a register (like a cloakroom book) of how many tickets with each number we have already seen:
- Ticket
xarrives. Look up how manyS − xtickets have been seen. Add that many pairs. - Record
xin the register.
In C++ the register is a map, which stores key → value pairs in sorted order; each lookup or update takes about log n steps. One pass, one lookup per ticket: O(n log n).
map<ll, ll> seen;
ll pairs = 0;
for (ll x : a) {
if (seen.count(S - x)) pairs += seen[S - x];
seen[x]++;
}
| n | Brute force | Register (map) |
|---|---|---|
| 50,000 | pairs = 1293, ~0.9 s |
pairs = 1293, ~40 ms |
| 200,000 | Time Limit Exceeded | pairs = 20171, ~0.2 s |
Both give the same count on the same tickets, which is a quick check that the fast version is right.
Why record x after the lookup? So a ticket never pairs with itself (for example x = 5, S = 10).
The accepted solution and edge cases
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
ll S;
cin >> n >> S;
map<ll, ll> seen;
ll pairs = 0;
for (int i = 0; i < n; i++) {
ll x;
cin >> x;
if (seen.count(S - x)) pairs += seen[S - x];
seen[x]++;
}
cout << pairs << '\n';
return 0;
}
| Input | Output | Why |
|---|---|---|
5 7 / 1 6 3 4 3 |
3 |
the sample |
4 10 / 5 5 5 5 |
6 |
all equal: every ticket pairs with every other, 4·3/2 = 6 |
Edge case: an input at the extreme of the rules. With 200,000 equal tickets, the answer is n(n−1)/2 ≈ 2·10^10, which does not fit in an int. So pairs must be long long, even though every ticket number fits in an int.
Brute force vs optimal
| Approach | Time | Extra memory | n = 2·10^5 |
|---|---|---|---|
| Every pair | O(n²) ≈ 2·10^10 | O(1) | TLE |
Register with map |
O(n log n) | O(n) | AC (~0.2 s) |
Register with unordered_map |
O(n) average | O(n) | AC (can be attacked by anti-hash tests on some judges) |
| Sort + two pointers | O(n log n) | O(1) beyond the array | AC |
Solution in Java and Python
Java
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
long S = Long.parseLong(st.nextToken());
st = new StringTokenizer(br.readLine());
HashMap<Long, Long> seen = new HashMap<>();
long pairs = 0;
for (int i = 0; i < n; i++) {
long x = Long.parseLong(st.nextToken());
pairs += seen.getOrDefault(S - x, 0L);
seen.merge(x, 1L, Long::sum);
}
System.out.println(pairs);
}
}
Python
import sys
from collections import defaultdict
def main():
data = sys.stdin.buffer.read().split()
n, S = int(data[0]), int(data[1])
seen = defaultdict(int)
pairs = 0
for tok in data[2:2 + n]:
x = int(tok)
pairs += seen[S - x]
seen[x] += 1
print(pairs)
main()
Read ALL the constraints
- Max n → the complexity (the table above).
- Max values →
intorlong long, for sums, products and even counts. - Sum of n over all tests → the total work (episode 2).
- Memory limit → 256 MB ≈ 6·10^7
ints ≈ 3·10^7long longs. - Strangely small limits (
n ≤ 20,k ≤ 5) → a hint that the solution uses them (bitmasks, small loops).
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
Double loop when n ≤ 2·10^5 |
Time limit exceeded on test 9 | 2·10^10 steps ≫ 10^8 per second | Find an O(n log n) idea |
int pairs; |
Wrong answer (negative count) | The answer can reach 2·10^10 | long long pairs; |
Recording x before looking up S − x |
Wrong answer when 2x = S |
A ticket pairs with itself | Look up first, then record |
| Only testing the sample | WA/TLE on hidden tests | Samples are tiny | Test max n and all-equal values |
Fancy algorithm when n ≤ 100 |
(no error) wasted time, more bugs | Brute force fits | Simplest thing that fits |
Mini project: a complexity stopwatch
Take the timing program and run the brute force for n = 10^4, 2·10^4, 4·10^4 and 8·10^4. Write the times in a table and check that each doubling multiplies the time by about 4. Then do the same for the map version and check it roughly doubles.
Practice
-
n ≤ 18. What complexity do you expect?Solution
O(2^n · n): about 4.7·10^6, so trying every subset is intended. -
n ≤ 3000, time limit 1 s. Is O(n²) fine? O(n² log n)?Solution
n² = 9·10^6: fine. n² log n ≈ 10^8: borderline but usually fine in C++. -
Solve Ticket Pairs with sorting and two pointers.
Solution
Sort `a`. Put `l = 0`, `r = n − 1`. While `l < r`: if `a[l] + a[r] < S`, `l++`; if greater, `r--`; if equal and `a[l] == a[r]`, add `(r − l + 1)(r − l)/2` and stop; otherwise count the run of equal values at `l` (`cl`) and at `r` (`cr`), add `cl · cr`, and move both pointers past their runs. -
Count pairs with
a[i] + a[j] = Sandi < jwheren ≤ 2000. Which approach do you write in a contest?Solution
The double loop: 2·10^6 checks, simplest to get right.
Quick quiz
n ≤ 10^5, time limit 1 s. Which complexity passes?
A) O(n²) B) O(n·√n) C) O(2^n) D) O(n³)
Answer
B. n·√n ≈ 3.2·10^7 steps, well under 10^8. n² = 10^10 is a hundred times too slow; 2^n and n³ are hopeless.
Interview questions
- What does O(n log n) mean in plain words? (Doubling n slightly more than doubles the work; sorting is the classic example.)
- Why is the rule "10^8 operations per second" only approximate? (It depends on the operation's cost, memory access patterns, the language and the judge machine.)
- How would you find all pairs summing to S faster than O(n²)? (Hash map of seen values, or sort + two pointers.)
- Why can the count of pairs overflow even if every element fits in an int? (The count can reach n(n−1)/2.)
Glossary
| Term | Meaning | Example |
|---|---|---|
| Constraints | Limits on the input values | n ≤ 2·10^5 |
| Operation (step) | One simple action: a comparison, an addition, an array access | a[i] + a[j] == S |
| Time complexity | How the number of steps grows with input size | O(n²) |
| Big-O | Notation for growth, ignoring constant factors | O(n log n) |
| Brute force | Trying every possibility directly | every pair (i, j) |
| Time Limit Exceeded (TLE) | The program ran longer than allowed | the double loop at n = 2·10^5 |
mt19937 |
C++'s Mersenne Twister random number generator | mt19937 rng(42); |
| Seed | The starting value of a random generator; same seed, same numbers | 42 |
map |
A sorted key → value container with O(log n) operations | map<ll, ll> seen; |
unordered_map |
A hash-based key → value container, O(1) on average | unordered_map<ll, ll> |
| Edge case | An input at the extreme of the rules | all tickets equal |
| Space complexity | How much memory the algorithm needs as n grows | O(n) for the map |
| Two pointers | Two indices moving through sorted data | l and r |
Summary
- Correct is not enough: the solution must fit the time limit on the largest test.
- Count steps and compare with about 10^8 per second.
- Big-O is how the work grows; O(n²) means 2× n → 4× time.
- Memorise the table: 10 → n!, 20 → 2^n, 500 → n³, 5000 → n², 2·10^5 → n log n, 10^7 → n, 10^18 → log n.
- Turning "check every partner" into "look up the one partner you need" removed the inner loop.
- Check whether the answer needs
long long, and test the extremes.
Next episode: every verdict (WA, TLE, MLE, RE) and how to debug each.